Розпишемо алгоритм по кроках

· Х - початковий стан;

· У - проміжний стан;

· 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;

Схожі статті