Простая рекурсия

В Паскале допускается, чтобы функция вызывала саму себя. Такой способ вы­зова называется простой рекурсией. Классическим примером использования ре­курсии является вычисление факториала целого положительного числа — n!.

Пример 50. Найти факториал N!, используя рекурсивную функцию FACT. Вычисление факториала осуществляется по рекуррентной формуле:

В этой программе рекурсивный процесс с каждым шагом упрощает задачу, сво­дя n! с помощью рекуррентной формулы к (n-1)! и далее до 1!, который по определению равен единице. Это событие и является решением, обеспечивающим завер­шение процесса вычисления факториала.

PROGRAM PR50;

VAR N: REAL;

FUNCTION FACT(A: REAL): REAL;

BEGIN

IF (A = 0) OR (A = 1) THEN FACT := 1

ELSE FACT := A * FACT(A - 1) {Рекуррентная формула}

END;

BEGIN

WRITELN(‘Введите число N');

READLN (N);

WRITELN(N: 3:0, '!=', FACT(N): 7:0)

END.

Графическими алгоритмами, в том числе и структурограммой, работу рекурсив­ной функции объяснить невозможно по той причине, что в оперативной памяти воз­никает и параллельно существует семейство копий такой функции с разными исход­ными данными. Пусть мы решаем пример 6 для 5! Временная диаграмма вычисли­тельного процесса представлена на рис. 5.3.

При вводе параметра N = 5 в момент времени Т₁, происходит вызов рекурсив­ной функции FACT(5) из тела основной программы. Управление передается функ­ции. В соответствии с рекуррентной формулой в теле рекурсивной функции при вызове функции выполняется оператор FACT := А * FACT(A - 1) для А = 5, то есть вызывается функция FACT(4). Это происходит в момент времени Т₂. В оператив­ной памяти создается еще один образ функции FACT и в качестве входного пара­метра ей дается значение А = 4. С момента времени Т₂ по Т₉ функция FACT(5) находится в пассивном состоянии, то есть существует, но не работает. С момента времени Т₂ по Т₃ выполняются операторы функции FACT(4).

Рис. 5.3. Семейство копий для рекурсивной функции FACT(5)

Происходит анализ параметра А, и поскольку А = 4, вызывается функция FACT(3) в момент времени Т₃. В оперативной памяти создается еще один образ функции FACT и в качестве входного параметра ей дается значение А = 3. С мо­мента Т₃ и до момента Т₈ функция FACT(4) становится пассивной, поскольку управление она передала функции FACT(3). Функция FACT(3) вызывает функ­цию FACT(2), а та в свою очередь функцию FACT( 1). Функция FACT(1) является последней в семействе, то есть она возвращает значение равное 1 в функцию FACT(2) в момент времени T₆. В этот момент код функции FACT(l) удаляется из оперативной памяти. Функция FACT(2) становится активной, вычисляет значе­ние равное 2 и в момент времени Т₇ передает управление FACT(3). Функция FACT(2) в момент времени Т₇ удаляется из памяти. Этот процесс продолжается до момента времени Т₁₀, когда рекурсивная функция завершает свою работу, возвра­щая вычисленное значение коду основной программы.

Опыт изучения рекурсивных функций показывает, что, несмотря на приведен­ное выше подробное описание, программист все же плохо чувствует работу рекур­сивных программ, поскольку принцип их действия выходит за рамки интуитивно­го понимания процессов программирования.