Повторение
О рекурсии
1. Подпрограмме на Паскале (т.е. функции или процедуре) разрешено обращаться к самой себе - либо напрямую, либо через цепочку вызовов других подпрограмм, приводящую к первоначальной точке вызова.
О подпрограмме, которая вызывает саму себя, говорят, что она рекурсивна.
Многие математические функции и алгоритмы, будучи запрограммированы на Паскале, наиболее естественно выражаются именно в рекурсивной форме. В большинстве случаев рекурсивное решение задачи получается достаточно простым, но в то же время оказывается крайне неэффективным в сравнении с итеративной реализацией этого алгоритма.
2. Рекурсивное определение какого-либо понятия или процесса должно содержать два обязательных элемента: 1) условие прекращения рекурсии, задающее некоторое фиксированное значение для одного или нескольких простых этапов вычисления; 2) выражение более сложного этапа вычислений в терминах менее сложного. Правильно организованный рекурсивный процесс развивается таким образом, что любая сколь угодно сложная ситуация в конце концов сводится к условию прекращения рекурсии.
3. В качестве примера, демонстрирующего рекурсию, часто используют функцию факториала, определяемую как произведение всех натуральных чисел от 1 до n (в математической нотации n!). Например, 4! = 1 . 2 . 3 .
4 = 24. Этому вычислительному процессу можно придать и рекурсивную трактовку. Роль условия выхода из рекурсии здесь играет равенство 0! = 1 или 1! = 1. Выражение сложного этапа через более простой имеет вид n! = (n - 1)!
4. В подпрограмме на Паскале рекурсивный вызов внешне выглядит точно так же, как и вызов любой другой подпрограммы. Так, в функции fac, вычисляющей значение "n-факториал", ее тело имеет следующий вид:
if (n = 0) or (n = 1) then
fac := 1 {завершение рекурсии}
{иначе - рекурсивный вызов}
else fac := fac(n - 1)*n
Имя функции fac получает значение 1, если n равно 0 или 1; если же n больше единицы, то значение fac определяется как произведение n и значения, полученного от рекурсивного обращения к fac(n - 1).
