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

– У шухлядці…"

У цьому старому анекдоті не називається справжнє джерело грошей. Якщо через A, B, C позначити чоловіка, його дружину та шухлядку, то пересування грошей зображається так: A C B A …, і справжнє джерело грошей залишається невідомим.

Щоб подібна "дурна нескінченність" не виникала в рекурсивному означенні, повинні виконуватися умови:

1.множина означуваних об'єктів є частково упорядкованою;

2.кожна спадна за цим упорядкуванням послідовність елементів закінчується деяким мінімальним елементом;

3.мінімальні елементи означаються нерекурсивно;

4.немінімальні елементи означаються за допомогою менших від них елементів.

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

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

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

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

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

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

3.якщо 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-е число Фібоначчі;

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