Паскаль: рекурсивні означення та підпрограми, Детальна інформація

обчислення 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\xF0A3 1 або n=0 або n=m; у противному разі

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

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