Чи траплялось Вам колись
зазирнути у дзеркало, напроти якого стоїть таке саме дзеркало? Не правда дивна
картина? В першому дзеркалі ми побачимо відображення із протилежного дзеркала,
в якому, в свою чергу, видно зображення першого дзеркала і т.д. Коли скінчиться
цей процес? А жартівливий віршик "У попа була собака..."?
У математиці часто зустрічаються
такі розрахунки, коли наступне значення величини обчислюється через попереднє.
Наприклад, для того, щоб обчислити значення степеню x^n необхідно знати
значення x^(n-1), для чого в свою чергу необхідно знати значення x^(n-2) і т.д.
Якщо спробувати запрограмувати цей процес, не порушуючи логіку міркувань та
оформлюючи його підпрограмою (наприклад, функцією), нам прийдеться для
обчислення значення xn викликати функцію обчислення
степеню x^(n-1) і помножити це значення на величину х. Тобто ми приходимо до
такого явища, як виклик підпрограми в середині самої підпрограми.
Рекурсією називається
така ситуація, коли підпрограма (процедура або функція) викликає сама себе.
Типова конструкція рекурсивної процедури
повинна мати наступний вигляд:
Procedure Rec (t:integer);
Begin
<Дії
на початку рекурсії>
If <Перевірка умови>
Then Rec(t+1);
<Дії
на виході з рекурсії>
End;
Саме головне при написанні рекурсії
усвідомити, як правильно задати умову, яка буде заглиблювати нас у рекурсію
або, навпаки, виводити з неї.
Розглянемо приклад рекурсивного виклику на
обчисленні степеня числа х^n, де х - будь-яке дійсне число, а n - ціле, додатне
число. Очевидно, що постає питання, коли і як припинити цей процес? У даному
випадку зупинкою для обчислень буде обчислення x0, так як відомо, що нульова
степінь будь-якого числа дорівнює 1. Тобто рекурсивна функція для обчислення
степеня числа буде мати наступний вигляд:
Function Step(x:real; n:integer):real:
Begin
If n = 0
then Step:=1
else Step:=Step(x,n-1)*x;
End;
Проаналізуємо роботу цієї функції на прикладі
знаходження значення 23. При першому виклику функції значення змінних буде
дорівнювати відповідно:
x = 2
n = 3.
Так як значення n не дорівнює 0 спрацює гілка else, тобто почне виконуватись такий оператор
Step:=Step(x,n-1)*x;
де x буде дорівнювати 2, і n - теж 2.
Цей оператор містить виклик функції step, тому виконання підпрограми перерветься і виконається
виклик тієї ж самої функції step, але з параметрами
x=2 та n=1. При виконанні повторного виклику функції ситуація повториться, так
як n поки ще не дорівнює 0 і тільки на четвертому виклику функції step параметр n досягне нульового значення, після чого
спрацює гілка then, яка присвоїть значення функції 1.
У даній найпростішій рекурсії ніякі дії при
вході в рекурсію не відбуваються, але при виході з рекурсії необхідно знати
точки, з яких здійснювався вхід в чергову функцію, щоб мати можливість
повернутися в них. Ці точки виклику запам'ятовуються у спеціалізованій пам'яті,
що зветься стек, і потім по черзі являються тими точками повернення, які
використовує система при зворотному русі з рекурсії.
Очевидно, що виконання рекурсії є досить
складним процесом, який крім того вимагає суттєвих витрат додаткових ресурсів
(що найменше пам'яті). Тому використання рекурсії не рекомендується в тих
випадках, коли вона просто замінюється ітеративним процесом (як в наведеному
прикладі). Однак, існує велика кількість досить складних алгоритмів, які без
використання рекурсії мають дуже заплутану логіку роботи.
Контрольні запитання:
1.Глобальні і локальні
параметри.
2. Що таке рекурсія.
3. Параметри-процедури і параметри-функції.