Factorial(3)

Factorial(2)

Factorial(1)

5 * 4 * 3 * 2 * 1 = 120

В данном случае реализована так называемая нисходящая рекурсия: вызов Factorial(5) означает, что функция Factorial вызывает себя раз за разом: Factorial(4), Factorial(3), … до тех пор, пока не будет достигнута терминальная ситуация – ситуация окончания рекурсии. При каждом вызове текущие вычисления откладываются, локальные переменные и адрес возврата остаются в стеке. Терминальная ситуация Factorial := 1 достигается при n = 0. При этом рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных в данный момент копий функции: начинает строиться ответ n*Fact(n-1). Сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты: 1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1 – передаются вызывающим функциям.

Рекурсивная функция, вычисляющая n-й член ряда Фибоначчи, может иметь вид:

Function Fibo(n: Word): Word;

Begin

If (n=1) Or (n=2)

Then Fibo := 1 выход из рекурсии

Else Fibo := Fibo(n-2) + Fibo(n-1); рекурсия

End;

Мы рассмотрели непосредственную рекурсию – функция вызывает саму себя. Помимо непосредственной, возможна косвенная рекурсия – функция Func_1 вызывает функцию Func_2, а функция Func_2, в свою очередь – функцию Func_1. Но как описать две функции, вызывающие одна другую? Ведь по правилам Паскаля подпрограмма обязательно должна быть объявлена до своего использования. В этом случае используется опережающее описание с помощью директивы Forward. При объявлении подпрограммы указывается только ее заголовок со списком формальных параметров и директивой Forward, а тело создается далее без повторного описания этих параметров: