Рекурсивные подпрограммы

В ряде приложений алгоритм решения задачи требует вызова подпрограммы из раздела операторов той же самой подпрограммы, т.е. подпрограмма вызывает сама себя. Такой способ вызова называется рекурсией. Рекурсия полезна прежде всего в тех случаях, когда основную задачу можно разделить на подзадачи, имеющие ту же структуру, что и первоначальная задача. Подпрограммы, реализующие рекурсию, называются рекурсивными. Для понимания сути рекурсии лучше понимать рекурсивный вызов как вызов другой подпрограммы.

Приведенная ниже программа содержит функцию Factorial для вычисления факториала. Напомним, что факториал числа определяется через произведение всех натуральных чисел, меньших либо равных данному (факториал числа 0 принимается равным 1):

X! = 1 * 2 * ... * (X – 2) * (X – 1) * X

Из определения следует, что факториал числа X равен факториалу числа (X – 1), умноженному на X. Математическая запись этого утверждения выглядит так:

X! = (X – 1)! * X, где 0! = 1

Последняя формула используется в функции Factorial для вычисления факториала:

function Factorial(X: Integer): Longint;begin if X = 0 then // Условие завершения рекурсии Factorial := 1 else Factorial := Factorial(X - 1) * X;end;

Вызов функции выглядит следующим образом:

var f: longint;begin f:=Factorial(4); // 4! = 1 * 2 * 3 * 4 = 24 ShowMessage(inttostr(f));end;

При написании рекурсивных подпрограмм необходимо обращать особое внимание на условие завершения рекурсии, иначе рекурсия окажется бесконечной и приложение будет прервано из-за ошибки переполнения стека. (Хорошо бы нарисовать схему рекурсии)

Решить эту же задачу с помощью цикла.

Function Fact(N:integer) : LongInt; Var i : integer; //переменная цикла Res : LongInt; //результат Begin Res := 1; for i := 1 to N do res := Res*i; NonResFact := Res;End;

Бывает встречается такая рекурсия, когда первая подпрограмма вызывает вторую, а вторая — первую. Такая рекурсия называется косвенной. Очевидно, что записанная первой подпрограмма будет содержать еще неизвестный идентификатор второй подпрограммы (компилятор не умеет заглядывать вперед). В результате компилятор сообщит об ошибке использования неизвестного идентификатора. Эта проблема решается с помощью упреждающего (предварительного) описания процедур и функций.