Приклади рекурсивних програм

Для деяких задач рекурсія є найбільш природним та найбільш ефективним способом розв'язання. Розглянемо два класичні приклади таких задач: гру «Ханойські вежі» (приклад 4.9) та задачу швидкого піднесення до степеня (приклад 4.10).

Приклад 4.9

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

Алгоритм гри «Ханойські вежі»

1.Перенести вежу з п-1 дисків з першого стрижня на проміжний.

2.Перенести n-й диск з першого стрижня на третій.

3.Перенести вежу з п-1 дисків з проміжного стрижня на третій.

Таким чином, задачу перенесення п дисків було зведено до задачі перенесення п-1 дисків. Рекурсивна процедура Move (n, from, temp, on), що реалізує перенесення n дисків із стрижня from (вхідний стрижень) на on (цільовий стрижень) з використанням стрижня temp як проміжного. Зазначимо, що ролі стрижнів під час гри змінюються. Якщо спочатку проміжним є другий стрижень, то при виконанні кроку 1 алгоритму проміжним стає третій, а при виконанні кроку 3 — другий стрижень

program ех8_8; {Ханойські вежі)

var n:integer; {кількість дисків)

{=========== ініціалізація даних ==============}

procedure Init;

begin

writeln (‘Hanoy towers’);

writeln ('enter number of disk ‘);

readln(n);

writeln (‘transport process:’);

end;

{==========перенесення дисків===============}

procedure Move (i:integer; from,temp.on;char);

{i- кількість дисків; from,temp.on - назви стрижнів}

begin

if i>0 then {перенести один диск та вийти із процедури)

begin

{перенести і-1 дисків із вхідного стрижня на проміжний}

Move(i-l, from, on, temp);

{перенести найбільший диск із вхідного стрижня на цільовий} writeln(‘move disk ', і, ' from ', from,' to ', on);

{перенести і-1 дисків із проміжного стрижня на цільовий}

Move(i-l, temp, from, on);

end;

end;

{=================основна програма ===================}

begin

Init;

Move (n, '1','2','З'); {виклик рекурсивної процедури}

end.