5 * 4 * Factorial(3)

5 * 4 * 3 * Factorial(2)

5 * 4 * 3 * 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, а тело создается далее без повторного описания этих параметров:

Program Primer;

Uses CRT;

Var i: Integer; описание переменных головной программы

Function Func_1(x: Integer): Integer; Forward; опережающее объявление функции Func_1

Function Func_2(y: Integer): Integer; описание функции

Var k: Integer; Func_2

Begin

………

k := Func_1(y); обращение к функции Func_1

………

End;

Function Func_1; описание функции

Var n: Integer; Func_1 без списка формальных

Begin параметров

……….

n := Func_2(x); обращение к функции Func_2

……….

End;

Begin основная программа

……..

i := Func_1(i); обращение к функции Func_1

…….. в основной программе

End.

Примеры:

1.Составить функцию, рекурсивно определяющую значение биномиального коэффициентапри 0<m<nпо формулам:

= = 1, = +

Function Binom(m, n: Word): Word;

Begin

If (m=0) Or (m=n)

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

Else Binom := Binom(m, n-1) + Binom(m-1, n-1) рекурсия

End;

2.Составить функцию, рекурсивно определяющую максимальный элемент в заданной части целочисленного массиваA_n, начиная сk-го и до n-го элемента:

Const n = 100;

Type TArray = Array [1..n] Of Integer;

………………………………………..

Function Max_element(a: TArray; k,n: Word): Integer;