Рекурсия

Замечания. В таблице описаны термины и понятия, связанные с рекурсией и используемые в информатике. Их оказалось чуть более 30. При этом многие понятия вводятся впервые. В то же время подобных слов и словосочетаний, активно используемых в математике порядка 300.

2. Корзина разнообразных задач

Как для конкретной задачи построить рекурсивный алгоритм её решения? - готовых

рецептов не существует. Некоторые практические рекомендации на этот счет приведены в [6, стр. 144]. Однако лишь ознакомление с достаточным количеством учебных рекурсивных алгоритмов позволит выработать определенную интуицию в выборе тактики и стратегии поиска и обнаружения спасательной рекурсии в незнакомой обстановке и заложить фундамент для освоения, совершенствования и отработки техники рекурсивного программирования. Общие рекомендации здесь могли бы быть такими. Пытаясь искать рекурсивное решение какой-либо задачи, следует опираться на одну из предлагаемых ниже именованных схем.

· Схема 1 - “увидеть”. Увидеть непосредственную рекурсию в определении объекта. Во многих задачах условия не просто задают её постановку, но делают это рекурсивно. Отсюда и рекурсивные программы, являющиеся точной копией условий задачи. Смотри задачи ??? .

· Схема 2 - “переформулировать”. Часто в условиях задачи не только не проглядывается рекурсия, но и сама задача неявляется алгоритмически сформулированной. Иногда её простая перефразировка, а чаще построение математической модели позволяют вдруг обнаружить первоначально скрытую рекурсию. Смотри задачи ???.

· Схема 3 - “обобщить (погрузить, вложить)”. Если из постановки задачи рекурсию извлечь не удаётся, то за счет перехода к её некоторому обобщению иногда это сделать можно. При этом предполагается, что из решения обобщенной задачи без особого труда может быть получено решение исходной задачи. Как правило, переход к обобщенной задаче происходит за счет введения дополнительных параметров. В некоторых случаях рассматриваемая схема может быть использована для перехода от одного типа рекурсии к другому. Смотри задачи ???.

· Схема 4 - “найти родственника”. Иногда к исходной задаче удается найти одну или несколько вспомогательных родственных к ней задач так, что в совокупности, взаимно дополняя друг друга, они уже будут определять вполне просматриваемую косвенную рекурсию. Смотри задачи

· Схема 5 - “обнаружить характеристическое свойство”. Пусть совокупность всех или части условий задачи оформлена в виде некоторого предиката над наборами входных данных и возможных результатов. Такой предикат определяет некоторое характеристическое свойство задачи. Формальная запись предиката с одной стороны позволяет проводить независимую “экспертную” проверку правильности работы ранее разработанных алгоритмов решения данной задачи, а с другой стороны, может оказать существенную помощь для отыскания новых рекурсивных алгоритмов её решения. При этом иногда целесообразно преобразовать предикат, то есть переформулировать характеристическое свойство задачи так, чтобы из него можно было извлечь какой-либо иной алгоритм. В любом случае, следует помнить, что характеристические свойства не всегда определяют исходную задачу однозначно.

· Схема 6 - “перенести часть условий в проверку”. Иногда при рассмотрении всех условий задачи рекурсия в явном виде сразу не обнаруживается, но удаление части условий приводит к новой вспомогательной задаче, рекурсивный алгоритм решения которой строится без особых затруднений. В этом случае, чтобы узнать, является ли полученный для новой задачи ответ (ответы) решением исходной задачи, необходимо проверить выполняются ли для него ранее удаленные условия или нет. Если решение задачи сводится к вычислению значения истинности некоторого предиката, непосредственно построенного из конъюнкции условий задачи на наборах входных данных, то описанная схема допускает возможность проверки выполнимости удаляемых условий как до использования рекурсивного алгоритма решения вспомогательной задачи, так и после этого. Смотри задачи ???.

Остановимся еще на одном важном моменте. Последовательность рекурсивных обращений за конечное число шагов обязательно должна приводить нас к одному из индикаторов завершения вычислений, расположенных в базе (см. табл. 3.1, где совокупность предварительных вычислений, соответствующая прямому ходу алгоритма Â, обозначена через f). В дальнейшем остается лишь провести отложенные вычисления. Этим рекурсивные вычисления по существу отличаются от метода последовательных приближений. Однако нельзя всегда рассчитывать на окончание рекурсивного алгоритма за конечное число шагов, как на нечто само собой разумеющееся. Иногда установление этого свойства для определенного подмножества значений пространства параметров требует значительных усилий в проведении подчас непростых рассуждений.

Таблица 3.1. Схематическое изображение последовательности рекур-

сивных обращений и формирования полной рекурсивной траектории

В оставшейся части данного пункта рассматривается серия простых учебных демонстрационных задач, решения которых получаются с помощью рекурсивно определенных алгоритмов. Во многих случаях детально обсуждаются описанные выше схематические приемы поиска этих алгоритмов. В основном все программы-функции написаны на языке программирования вычислительной среды Mathcad. Часть программ написана на языке Object Pascal 5.0 системы объектного визуального программирования Delphi 5. Для некоторых задач предлагается несколько вариантов программ. Приводятся контрольные примеры. Заметим, что, ввиду разноплановости предложенных задач, многие из них могут служить отдельными темами, собирающими вокруг себя родственный содержательный материал по рекурсии для отработки техники рекурсивного программирования в рамках конкретного направления.

Результатом проработки материала данного пункта должно стать убеждение, что писать рекурсивные программы, как правило, несложно, а получаемые при этом тексты весьма компактны и, по причине отсутствия в них диких зарослей языковых украшательств, легко читаются. Нам представляется, что читатель вряд ли откажет себе в удовольствии написать собственные программы-функции решения многих из приведенных задач или их обобщений.

3.1 Факториал

Задача 1. Составить программу-функцию вычисления факториала целого неотрицательного числа n.

Решение. Для целых неотрицательных чисел n факториал n обозначается через n! и определяется так:

В данном случае параметризация задачи осуществлена в её постановке. Остается лишь ввести более приемлемое для нас обозначение искомой функции. Пусть это будет facto(n). Тривиальные случаи, для которых задача решается без рекурсивных вызовов, также очевидны: facto(0)=1, facto(1)=1. Они и составляют базу рекурсии. Декомпозиция по параметру n реализуется по формуле: facto(n) = n×facto(n–1) (n = 1, 2, …). Поэтому вычисления facto(n) можно организовать так:

 Скачать реферат