Это метод определения функции, процедуры, языковой последовательности или алгоритма решения задачи посредством этой же функции, процедуры и т. п.
Основное требование к рекурсии — возможность ее логического завершения.
Пример: вычисление факториала положительного числа n.
Различают следующие виды рекурсий.
1. Линейная рекурсия. Вызов рекурсивной функции по любой из всех возможных ветвей алгоритма встречается не более одного раза.
Пример: подсчет конечной суммы.
Пример: деление нацело положительных целых чисел a и b.
2. Нелинейная (конечная, хвостовая — tail (англ.)) рекурсия. Вызов рекурсивной функции по любой из всех возможных ветвей алгоритма является самым внешним (последним) действием. Перед началом выполнения нового рекурсивного вызова обработка предыдущего полностью заканчивается. (Значения локальных переменных и фактических параметров рекурсивной функции могут быть сброшены, а сами переменные повторно использованы.)
Пример: деление нацело положительных целых чисел a и b.
Первый вызов div(a, b, 0). Частное возвращается через последний параметр функции.
3. Каскадная (нелинейная, древовидная) рекурсия. Вызов рекурсивной функции по любой из всех возможных ветвей алгоритма встречается более одного раза.
Пример: вычисление чисел Фибоначчи.
Леонардо Пизанский (Фибоначчи) решал задачу о размножении кроликов. Каждый месяц в каждой паре кроликов самка приносит потомство — самца и самку. Нужно найти число кроликов в конце года, если в его начале была одна новорожденная пара, и в течение года кролики не умирали.
Пример: вычисление биноминальных коэффициентов.
4. Удаленная рекурсия. Вызов рекурсивной функции в ее теле является фактическим параметром.
Пример: вычисление функции Аккермана (важен порядок проверки условий).
Примечание. Аккерман построил свою функцию для опровержения тезиса, что всюду определенные функции с интуитивно очевидными алгоритмами получения значения обязательно являются примитивно-рекурсивными (по Гильберту примитивно рекурсивной считается вычислимая функция, которая получается с помощью конечного применения операций подстановки и примитивной рекурсии).
5. Взаимная рекурсия. Вызов рекурсивной функции содержится в ее некоторой внутренней функции.
Для того чтобы рекурсия не приводила к зацикливанию, в тело рекурсивного метода всегда встраивается оператор выбора, одна из ветвей которого не содержит рекурсивных вызовов. Если рекурсивный вызов встречается только один раз, то рекурсию можно заменить обычным циклом. Это приводит к более эффективной программе, поскольку реализация рекурсии требует временных затрат и работы со стековой памятью.
Дата добавления: 2015-04-11; просмотров: 76 | Поможем написать вашу работу | Нарушение авторских прав |