begin

if n = 1 then f := 1

else f := n * f ( n-1 )

end;

При імітації виконання викликів рекурсивних підпрограм їх локальні змінні позначають у такий спосіб. Якщо підпрограма F викликана з програми, то її локальна змінна X позначається F.X. За виконання кожного рекурсивного виклику підпрограми F, указаного в її тiлi, з'являється нова змiнна X. Вона позначається дописуванням префікса "F." до позначення змінної X у попередньому виклику: F.F.X, F.F.F.X тощо.

Приклад 7. Імітацію виконання виклику f(2) функції з прикладу 9.6 можна податі таблицею:

що виконується | стан пам'яті

Виклик f(2) | f.n | f.f 

2 | ?

обчислення n=1: false | 2 | ?

початок f := n*f(1) | 2 | ?

виклик f(1) | 2 | ? | f.f.n | f.f.f 

2 | ? | 1 | ?

обчислення n=1: true | 2 | ? | 1 | ?

f := 1 | 2 | ? | 1 | 1

повернення з виклику f(1) | 2 | ?

закінчення f := n*f(1) | 2 | 2

Приклад 8. Найбільший спiльний дільник НСД(a,b) натуральних a і b можна обчислити рекурсивно на основі таких рівностей:

якщо b = 0, то НСД(a, b) = a,

якщо a mod b = 0, то НСД(a, b) = b,

якщо a mod b > 0, то НСД(a, b) = НСД( b, a mod b ).

Цьому означенню відповідає така рекурсивна функція обчислення НСД:

function GCD ( a, b : integer) : integer;

{ Greatest Common Divisor – Найбільший Спiльний Дільник}

begin

if b=0 then GCD:=a else

if a mod b=0 then GCD := b

else GCD := GCD ( b, a mod b)

end;

З рекурсивними підпрограмами пов'язано два важливих поняття – глибина рекурсії та загальна кількість викликів, породжених викликом рекурсивної підпрограми.

Розглянемо перше з них. У прикладі 9.6 наведено функцію обчислення n!. Очевидно, що її виклик із аргументом, наприклад, 4, закінчується лише після закінчення виклику з аргументом 3, а той, у свою чергу, після виклику з аргументом 2 тощо. Такі виклики називаються вкладеними. Отже, виклик із аргументом 4 породжує ще три вкладені виклики.

Взагалі, за виклику з аргументом n породжується ще n-1 виклик, і загальна кількість незакінчених викликів досягає n. Отже, максимальна кількість незакінчених рекурсивних викликів при виконанні виклику підпрограми називається глибиною рекурсії цього виклику.

За виконання виклику з глибиною рекурсії m одночасно "існують" m екземплярів локальної пам'яті. Кожний екземпляр має певний розмір, і якщо глибина буде надто великою, то автоматичної пам'яті, яку надано процесу виконання програми, може не вистачити.

Друге поняття можна назвати загальною кількістю вкладених викликів, породжених викликом рекурсивної підпрограми. Ця кількість значною мірою впливає на час виконання виклику. Проілюструємо це наступним прикладом.

Приклад 9. За властивостями трикутника Паскаля, біноміальний коефіцієнт C(m,n)=1 при m? 1 або n=0 або n=m; у противному разі

C(m,n)=C(m-1,n-1)+C(m-1,n).

Згідно цього означення напишемо рекурсивну функцію обчислення за m, n, де 0? n? m, біноміального коефіцієнта C(m,n):

function C(m, n : integer) : integer;

begin

if (m<=1) or (n=0) or (n=m) then C:=1

else C:= C(m-1, n-1)+C(m-1, n)

end;

Як бачимо, кожний виклик, у якому значення аргументів m>1, 0<n<m, породжує два вкладені виклики. У результаті відбуваються повторні обчислення тих самих величин. Наприклад, виконання виклику з аргументами (5,2) веде до того, що виклик із аргументами (3,1) виконується двічі, з аргументами (2,1), (1,0) та (1,1) – по тричі, а загальна кількість вкладених викликів сягає 18.

Неважко збагнути, що чим більше m і чим ближче n до m/2, тим більшою буде загальна кількість вкладених викликів. Ми не будемо точно означати її залежність від аргументів. Скажемо лише, що за n=mdiv2 або n=mdiv2+1 вона більше, ніж 2m/2. Наприклад, за m=60 це 230, або приблизно 109. Якщо навіть припустити, що за секунду можна виконати 106 викликів, то треба більше 1000 секунд, тобто приблизно 20 хвилин. Проте неважко написати рекурсивну функцію, виклик якої з аргументом m породжує не більше, ніж m/2 вкладених викликів (задача 9.7).

Отже, вживання рекурсивних підпрограм вимагає обережності та вміння оцінити можливу глибину рекурсії та загальну кількість викликів. Не завжди слід писати рекурсивні підпрограми безпосередньо за рекурсивним означенням. Принаймні, для обчислення біноміальних коефіцієнтів узагалі краще скористатися циклом (розділ 5.2). Справа в тім, що виконання кожного виклику підпрограми потребує додаткових дій комп'ютера, описаних у розділі 8. Тому "циклічний" варіант описання обчислень виконується, як правило, швидше від рекурсивного. Також не слід уживати рекурсію для обчислення елементів рекурентних послідовностей. За великої глибини рекурсії це взагалі може призвести до вичерпання автоматичної пам'яті та аварійного завершення програми.

У цьому розділі ми розглядаємо лише так звану пряму рекурсію, коли підпрограма містить виклики самої себе. У програмуванні зустрічається також і непряма рекурсія, коли підпрограма містить виклики інших підпрограм, а ті – виклики цієї підпрограми. Приклади непрямої рекурсії та реалізацію її в мові Паскаль ми розглянемо в розділі 21.

Задачі

4.* Виразити словами залежнiсть значення, що повертається функцією

function sumdi ( n : integer ) : integer;

begin

if n < 10 then sumdi := n

else sumdi := n mod 10 + sumdi ( n div 10 )

end,

від значення параметра. Вважається, що аргумент у її виклику невід'ємний.

5.* Написати процедуру друкування десяткових цифр цілого

а) у зворотному порядку, починаючи з молодших розрядів;

б) у звичайному порядку, починаючи зі старших розрядів.

6. Написати функцію обчислення за m, n, де 0? n? m, біноміального коефіцієнта