· Х - початковий стан;
· У - проміжний стан;
· Z - кінцевий стан. (Див. Рис. Вище)
1 крок - перенести (n-1) диск зі стрижня Х на стрижень У, використовуючи стрижень Z як допоміжний;
2 крок - перенести один нижній диск із стержня Х на стрижень Z;
3 крок - перенести (n-1) диск зі стрижня У на стрижень Z, використовуючи вільний стержень Х.
4. Таким чином маємо рекурсивний виклик процедури˸
Procedure Hanoi (n˸ word; x, y, z˸ char);
then writeln ( 'Перекласти', x, 'на', z)
Завдання на обчислення факторіала натурального числа.
Для того, щоб обчислити N. треба значення (N-1)! помножити на N, при цьому 1! = 1. У загальному вигляді це можна записати так˸
Для обчислення факторіала опишемо функцію˸
function factorial (n˸ integer) ˸ Longint;
else factorial˸ = n * factorial (n-1)
розглянемо послідовність викликів цієї функції для 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;