Для деяких задач рекурсія є найбільш природним та найбільш ефективним способом розв'язання. Розглянемо два класичні приклади таких задач: гру «Ханойські вежі» (приклад 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.