ПАСКАЛЬ: РЕКУРСИВНІ ОЗНАЧЕННЯ ТА ПІДПРОГРАМИ

г) обчислення із точністю  (див. приклад 4.4).2.* Дати нерекурсивне означення "91-функції Мак-Карті" F, означеної так: F(n)=n-10 при n>100, F(n)=F(F(n+11)) при n 100. Написати функцію обчислення F(n) при n<200.

3.* Розбиттям натурального числа n називається спосіб його подання у вигляді суми натуральних чисел. Наприклад, розбиттями числа 4 є 4, 3+1, 2+2, 2+1+1, 1+1+1+1. Означити рекурсивно функцію Q(n), що задає кількість розбиттів натурального n.

2. Рекурсивні підпрограми

За правилами мови Паскаль щодо області дії означень, тіло підпрограми може мiстити виклики підпрограм, чиї заголовки записані вище в тексті програми. Звідси випливає, що підпрограма може містити виклики самої себе – рекурсивні виклики. Виконання такого виклику нічим не відрізняється від виконання виклику будь-якої іншої підпрограми. Підпрограма з рекурсивними викликами називається рекурсивною.

Приклад 6. Напишемо рекурсивну функцію f за таким означенням функції "факторіал": n!=n (n-1)! за n>1, 1!=1 (вважається, що n>0).

function f ( n : integer ) : integer;

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.nf.f

2?

обчислення n=1: false2?

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

виклик f(1)2?f.f.nf.f.f

2?1?

обчислення n=1: true2?1?

f := 12?11

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