Распишем алгоритм по шагам

Положим:

· Х – исходное состояние;

· У – промежуточное состояние;

· Z – конечное состояние. (см. рис. выше)

1 шаг – перенести (n-1) диск со стержня Х на стержень У, используя стержень Z как вспомогательный;

2 шаг – перенести один нижний диск со стержня Х на стержень Z;

3 шаг – перенести (n-1) диск со стержня У на стержень Z, используя свободный стержень Х.

 

4. Таким образом имеем рекурсивный вызов процедуры:

Procedure Hanoi (n: word; x, y, z: char);

begin

if n=1

then writeln (‘Переложить’, x, ‘на’, z)

else

begin

hanoi (n-1, x, z, y); {1 шаг}

writeln (‘Переложить’, x, ‘на’, z); {2 шаг}

hanoi (n-1, x, z, y); {3 шаг}

end

end; {hanoi}

Задача на вычисление факториала натурального числа.

Для того, чтобы вычислить N!, надо значение (N-1)! умножить на N, при этом 1! =1. В общем виде это можно записать так:

Решение:

Для вычисления факториала опишем функцию:

function factorial (n: integer): Longint;

begin

if n=1

then factorial: =1

else factorial: =n*factorial (n-1)

end

end;

рассмотрим последовательность вызовов этой функции для n=5.

ü Первый вызов функции происходит в основной программе. Отметим, что при каждом обращении к функции будет создаваться свой набор локальных переменных (в данном случае в функции факториал имеется всего одна локальная переменная n). Для каждой локальной переменной на время работы функции выделяется память. После завершения работы функции эта память освобождается и переменные удаляются.

Так как , то управление передается на ветку Else и функции factorial присваивается значение n*factorial (n-1), то есть 5*factorial (4).

Происходит второй вызов функции factorial, с параметром 4. Этот процесс повторяется до тех пор, пока значение параметра не станет равным 1. Тогда n=1, а поэтому значение функции factorial=1.

Таким образом n=1 – это условие окончания рекурсии.

Управление передается в точку вызова, то есть в предыдущую функцию для n=2: factorial: =n* factorial (n-1), значит factorial: =2*1, следовательно, factorial (2)=2. Возвращаемся назад, поднимаясь «вверх» по цепочке рекурсивных вызовов. Таким образом, получаем значение factorial (5)=120.

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

1 вызов (n=5) 120

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

2 вызов (n-4)

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

3 вызов (n=3)

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

4 вызов (n=2)

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

5 вызов (n=1)