Сторінка
3

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

Отже, вживання рекурсивних підпрограм вимагає обережності та вміння оцінити можливу глибину рекурсії та загальну кількість викликів. Не завжди слід писати рекурсивні підпрограми безпосередньо за рекурсивним означенням. Принаймні, для обчислення біноміальних коефіцієнтів узагалі краще скористатися циклом (розділ 5.2). Справа в тім, що виконання кожного виклику підпрограми потребує додаткових дій комп'ютера, описаних у розділі 8. Тому "циклічний" варіант описання обчислень виконується, як правило, швидше від рекурсивного. Також не слід уживати рекурсію для обчислення елементів рекурентних послідовностей. За великої глибини рекурсії це взагалі може призвести до вичерпання автоматичної пам'яті та аварійного завершення програми.

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

Задачі

4.* Виразити словами залежнiсть значення, що повертається функцією

function sumdi ( n : integer ) : integer;

begin

if n < 10 then sumdi := n

else sumdi := n mod 10 + sumdi ( n div 10 )

end,

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

5.* Написати процедуру друкування десяткових цифр цілого

а) у зворотному порядку, починаючи з молодших розрядів;

б) у звичайному порядку, починаючи зі старших розрядів.

6. Написати функцію обчислення за m, n, де 0£ n£ m, біноміального коефіцієнта C(m,n) згідно з палимо, що C(m,n)=1 при n=0 або n=m; у противному разі

а) C ( m, n ) = C ( m-1, n-1 ) m / n;

б) C ( m, n ) = C ( m, n-1 ) ( m-n+1 ) / n;

в) C ( m, n ) = C ( m, n+1 ) ( n+1 ) / ( m-n ).

Підрахувати в кожному варіанті загальну кількість виконань викликiв функції при обчисленні коефіцієнта за m=6, n=2 та за m=8, n=5.

7.* Написати варіант функції обчислення C(m,n), при виконанні якого завжди відбувається не більше, ніж m/2 рекурсивних викликів.

8. Проімітувати звернення до функції Gcd (приклад 9.8) з аргументами

а)15 і 25; б) 13 і 21; в) 1024 і 729.

10.* Для довiльного n>0 указати числа an та bn такi, що при обчисленнi НСД(an,bn) за допомогою функції Gcd з прикладу 9.8 загальна кiлькiсть виконань викликiв дорiвнює n.

3. "Ханойські вежі"

На дошці є три голки: 1, 2, 3. На голці 1 розміщена вежа з n дисків; нижній диск має найбільший діаметр, а діаметр кожного наступного менший від попереднього. За один хід із будь-якої голки можна взяти верхній диск і перемістити на іншу, але дозволено класти диск лише на дошку або на диск більшого діаметра. Треба перемістити усю вежу з голки 1 на голку 3.

Ця гра називається "Ханойські вежі", оскільки за легендою з n=64 дисками її почали понад 1000 років тому ченці в одному монастирі поблизу Ханоя у В'єтнамі; коли вони закінчать її, настане кінець світу. Розв'язанням цієї гри-задачі є послідовність перенесень дисків. Написати програму друкування позначень цих перенесень.

Для перенесення вежі висотою n дисків з голки 1 на голку 3 необхідно перенести вежу висотою n-1 на голку 2, потім перенести нижній диск на голку 3 та перенести вежу з голки 2 на голку 3. При перенесенні вежі з 1 на 2 допоміжною є голка 3, а при перенесенні з 2 на 3 – голка 1. Інша послідовність дій неможлива. Отже, розв'язання задачі для вежі висотою n описується через розв'язання задачі для вежі висотою n-1.

Позначимо disk(a,b) перенесення одного диску з голки a на голку b, tow(h, a, b, c) – перенесення вежі висотою h з голки a на b з використанням голки c як допоміжної (tow – це скорочення від tower, або вежа). За h>1 виконання tow(h, a, b, c) зводиться до виконання

tow(h-1, a, c, b); disk(a, b); tow(h-1, c, b, a),

а за h=1 – до виконання

disk(a, b).

Отже, маємо програму:

program Hantow(input, output);

var n : integer;

procedure disk(f, t : integer);

begin writeln(f, '->', t) end;

procedure tow(h : integer; f, t, v : integer);

begin

if h=1 then disk(f, t) else

begin

tow(h-1, f, v, t); disk(f, t); tow(h-1, v, t, f)

end

end;

begin readln(n); tow(n, 1, 3, 2) end.

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

Визначимокількість переносів дисків як функцію f(n), де n – висота вежі. Очевидно, що f(1)=1, і що f(n)=2× f(n-1)+1. За принципом індукції неважко довести, що f(n)=2n-1. Значення f(64) дорівнює приблизно 1022. Якщо припустити, що кожної секунди ченці переносять один диск, то для переносу такої вежі потрібно приблизно 1015 років! Навіть якщо припустити, що комп'ютер здатний щосекунди друкувати по сто тисяч позначень переносів, то й тут знадобиться 1010 років. Кінець світу, мабуть, настане раніше…

4. "Індійський алгоритм" піднесення до степеня

Цей алгоритм обчислення натурального n-го (n>0) степеня цілого числа x виглядає зовсім просто:

за n=1 xn = x,

за n>1 xn = xn mod 2× (xn div 2)2.

Основна мета цього алгоритму – скоротити кількість множень при піднесенні до степеня. Наприклад, за цим алгоритмом x5=x× (x2)2, тобто достатньо три множення замість чотирьох: x× x× x× x× x. Одне множення економиться за рахунок того, що x2 зберігається як проміжне значення і множитися само на себе. Так само x10=1× (x5)2=(x5)2, що вимагає лише чотирьох множень (три з них для обчислення x5) замість дев'яти "лобових". Але тут доведеться зберігати спочатку x2, а потім x5.

Як бачимо, обчислення xn зводиться до обчислення xndiv2, запам'ятання його, піднесення до квадрату, та множення його на x за непарного n. Отже, обчислення xn описується рекурсивною функцією

function pow(x, n : integer) : integer;

var t : integer;

begin

if odd(n) then t:=x

else t:=1;

if n=1 then pow:=x

else pow:=t*sqr(pow(x, n div 2))