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

Неважко переконатися, що означення з прикладів 9.1–9.2 задовольняють ці умови, а з прикладів 9.3–9.5 – ні.

Для тих, кому не знайомі терміни "частково упорядкована множина" та "мінімальний елемент", дамо невелике пояснення.

Будь-яка множина пар, складених з елементів деякої множини, називається відношенням на цій множині. Наприклад, множина пар {(1,1), (1,2), (2,1)} на множині {1, 2}.

Відношення називається відношенням часткового порядку, якщо воно має такі властивості:

для кожного елемента a множини пара (a, a) є у відношенні;

якщо у відношенні є пара (a, b) з різними елементами a і b, то пари (b, a) там немає. При цьому ми кажемо, що a менше b. У множині можуть бути й непорівнювані елементи, що один з одним пару не утворюють;

якщо a менше b, а b менше c, то a менше c. Втім, елементів a, b, c таких, що a менше b, а b менше c, у множині може й не бути – при виконанні властивостей (1) і (2) відношення буде відношенням часткового порядку.

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

Очевидно, що в прикладі 9.1 кожні два елементи множини {1, 2, 6, …} порівнювані між собою, а мінімальним є 1. У прикладі 9.2 ідентифікатор менше іншого, якщо той утворюється з нього дописуванням символів наприкінці. Так, a менше a1 і aaa, а a1 і aa непорівнюванні. Ідентифікатор a – мінімальний. У прикладі 9.3 один вираз менше іншого, якщо він є його частиною. Так, 1 і 2 менше, ніж (1)+(2), а (1)+(2) менше, ніж ((1)+(2))+(1); мінімальними елементами є всі можливі сталі, і між собою вони непорівнювані.

Задачі

1. Дати рекурсивне означення функції, що задає:

а)* суму значень цифр десяткового подання натурального n;

б) n-е число Фібоначчі;

в) найбільший спільний дільник двох натуральних;

із точністю \xF065 (див. приклад 4.4).

2.* Дати нерекурсивне означення "91-функції Мак-Карті" F, означеної так: F(n)=n-10 при n>100, F(n)=F(F(n+11)) при n\xF0A3 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\xF0D7 (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.n f.f

  2 ?