к і з точки зору практичного програмування. Читач зможе дізнатися, як застосовувати на практиці алгоритми, що містять рекурсію, а головне коли коштує це робити. Важливо зберігати баланс між вишуканістю і простотою сприйняття, властиві рекурсивним алгоритмам, і складністю його реалізації на конкретній обчислювальній системі. br/>
1. Сутність рекурсії
Процедура або функція може містити виклик інших процедур або функцій. У тому числі процедура може викликати саму себе. Ніякого парадоксу тут немає - комп'ютер лише послідовно виконує зустрілися йому в програмі команди і, якщо зустрічається виклик процедури, просто починає виконувати цю процедуру. Без різниці, яка процедура дала команду це робити. p align="justify"> Приклад рекурсивної процедури:
procedure Rec (a: integer); a> 0 then (a-1); (a);;
Розглянемо, що відбудеться, якщо в основній програмі поставити виклик, наприклад, виду Rec (3). Нижче представлена ​​блок-схема, що показує послідовність виконання операторів. br/>В
Рис. 1. Блок схема роботи рекурсивної процедури. br/>
Процедура Rec викликається з параметром a = 3. У ній міститься виклик процедури Rec з параметром a = 2. Попередній виклик ще не завершився, тому можете уявити собі, що створюється ще одна процедура і до закінчення її роботи перша свою роботу не закінчує. Процес виклику закінчується, коли параметр a = 0. У цей момент одночасно виконуються 4 примірники процедури. Кількість одночасно виконуваних процедур називають глибиною рекурсії. p align="justify"> Четверта викликана процедура (Rec (0)) надрукує число 0 і закінчить свою роботу. Після цього управління повертається до процедури, яка її викликала (Rec (1)) і друкується число 1. І так далі поки не завершаться всі процедури. Результатом вихідного дзвінка буде печатка чотирьох чисел: 0, 1, 2, 3. p align="justify"> Ще один візуальний образ того, що відбувається представлений на рис. 2. br/>В
Рис. 2. Виконання процедури Rec з параметром 3. br/>
Складається з виконання процедури Rec з параметром 2 і друку числа 3. У свою чергу виконання процедури Rec з параметром 2 складається з виконання процедури Rec з параметром 1 і друку числа 2. І т. д.
В якості самостійного вправи подумайте, що вийде при виклику Rec (4). Також подумайте, що вийде при виклику описаної нижче процедури Rec2 (4), де оператори помінялися місцями. p align="justify"> Rec2 (a: integer); (a); a> 0 then (a-1);
end;
Зверніть увагу, що в наведених прикладах рекурсивний виклик стоїть всередині умовного оператора. Це необхідна умова для того, щоб рекурсія коли-небудь закінчилася. Також зверніть увагу, що сама себе процедура викликає з іншим параметром, не таким, з яким була викликана ...
