Сторінка
2
Приклад 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).
Завантажити реферат