Смекни!
smekni.com

Паскаль рекурсивні означення та підпрограми (стр. 1 из 3)

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

1. Рекурсивні означення

Часто кажуть, що рекурсивне означення – це коли щось означається з його ж допомогою. Фраза ця не зовсім точна, а вірніше, зовсім неточна. Кожне означення задає щось, і цим чимось є, як правило, об'єкти, що утворюють деяку множину.

Означення називається рекурсивним, якщо воно задає елементи множини за допомогою інших елементів цієї ж множини. Об'єкти, задані рекурсивним означенням, також називаються рекурсивними. Нарешті, рекурсія – це використання рекурсивних означень.

Приклади

1. Значення функції "факторіал" задаються виразом: 0!=1, n!=n×(n-1)!. Вони утворюють множину {1,2,6,…}: 0!=1, 1!=1, 2!=2, 3!=6, … . Усі її елементи, крім першого, означаються рекурсивно.

Отже, функція "факторіал" задається рекурентним співвідношенням порядку 1 і початковим відрізком 0!=1. Узагалі, будь-яке рекурентне співвідношення порядку k разом із завданням перших k елементів послідовності являє приклад рекурсивного означення.

2. Арифметичні вирази зі сталими та знаком операції '+' у повному дужковому записі (ПДЗ) задаються таким означенням:

1) стала є виразом у ПДЗ;

2) якщо E і F є виразами у ПДЗ, то (E)+(F) також є виразом у ПДЗ.

Такими виразами є, наприклад, 1, 2, (1)+(2), ((1)+(2))+(1). Всі вони, крім сталих, означаються рекурсивно.

Об'єкти, означені в прикладах 9.1–9.2, тобто значення функції "факторіал" та дужкові записи виразів, є рекурсивними.

У рекурсивних означеннях не повинно бути "зачарованих кіл", коли об'єкт означається за допомогою себе самого або за допомогою інших, але означених через нього ж.

Приклади

3. Змінимо означення функції "факторіал" на таке: n!=n×(n-1)! за n>0, 0!=1!. Спочатку значення функції від 1 виражається через її ж значення від 0, яке, у свою чергу, – через значення від 1. За цим "означенням" так і не дізнатися, чому ж дорівнює 1!.-

4. "У попа був собака, піп його любив, той з'їв шматок м'яса, піп його забив, і в землю закопав, і на камені написав, що у попа …" і так далі. Ця сумна історія не має кінця, і не можна сказати, що ж саме піп написав на камені.-

5. "– Де ти гроші береш?

– У шухлядці.

– А там вони звідки?

– Дружина кладе.

– А в неї звідки?

– Я даю.

– А де ти береш?

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

У цьому старому анекдоті не називається справжнє джерело грошей. Якщо через 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-е число Фібоначчі;

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

г) обчислення із точністю e (див. приклад 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.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,

якщо amodb = 0, то НСД(a, b) = b,

якщо amodb > 0, то НСД(a, b) = НСД( b, amodb ).

Цьому означенню відповідає така рекурсивна функція обчислення НСД:

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;