5.3. рекурсивні методи
Суть рекурсивних методів - зведення задачі до самої себе. Ви вже знаєте, що як в Паскалі, так і в Сі існує можливість рекурсивного визначення функцій і процедур. Ця можливість є спосіб програмної реалізації рекурсивних алгоритмів. Однак побачити рекурсивний шлях вирішення завдання (рекурсивний алгоритм) часто дуже непросто.
Розглянемо класичну задачу, відому в літературі під назвою «Ханойська вежа» (рис. 50).
На майданчику (назвемо її А) знаходиться піраміда, складена з дисків зменшується від основи до вершини розміру.
Цю піраміду в тому ж вигляді потрібно перемістити на майданчик В. При виконанні цієї роботи необхідно дотримуватися наступні обмеження:
• перекладати можна тільки по одному диску, взятому зверху піраміди;
• класти диск можна або тільки на підставу майданчики, або на диск більшого розміру;
• в якості допоміжної можна використовувати майданчик С.
Назва «Ханойська вежа» пов'язане з легендою, згідно з якою в давні часи монахи одного Ханойського храму взялися перемістити за цими правилами вежу, що складається з 64 дисків. Із завершенням їх роботи настане кінець світу. Ченці все ще працюють і, сподіваємося, ще довго будуть працювати!
Неважко вирішити цю задачу для двох дисків. Позначаючи переміщення диска, наприклад, з майданчика А на В так: А → В, напишемо алгоритм для цього випадку
А → С; А → В; З → В.
Всього 3 ходу! Для трьох дисків алгоритм довше:
А → В; А → С; В → С; А → В; З → А; З → В; А → В.
У цьому випадку вже потрібно 7 ходів.
Підрахувати кількість ходів (N) для k дисків можна за наступним рекуррентной формулою:
N (1) = 1; N (k) = 2х N (k - 1) + 1.
Наприклад, N (10) = 1023, N (20) = 104857. А ось скільки переміщень потрібно зробити Ханойська монахам:
Спробуйте прочитати це число.
Тепер складемо програму, за якою машина розрахує алгоритм роботи ченців і виведе його для будь-якого значення п (кількості дисків). Нехай на майданчику А знаходяться п дисків. Алгоритм рішення задачі буде наступним:
1. Якщо n = 0, то нічого не робити.
2. Якщо п> 0, то перемістити п - 1 диск на С через В;
перемістити диск з А на В (А → В)
перемістити п - 1 диск з З на В через А.
При виконанні пункту 2 послідовно будемо мати три стани (рис. 51).
Опис алгоритму має явно рекурсивний характер