Поняття рекурсії. Рекурсивні функції. приклад
Рекурсія (від латинського recursio - повернення) - це такий спосіб організації обчислювального процесу, при якому процедура або функція в ході виконання складових її операторів звертається сама до себе.
Для того, щоб таке звернення не було нескінченним, в тексті підпрограми повинно бути умова, по досягненню якого подальшого звернення не відбувається. таким чином, рекурсивне звернення може включатися тільки в одну з гілок.
У підпрограми мовою Паскаль немає ніяких обмежень на рекурсивні виклики підпрограм, необхідно тільки розуміти, що кожен черговий рекурсивний виклик призводить до утворення нової копії локальних об'єктів підпрограми і всі ці копії, відповідні ланцюжку активізованих і не завершених рекурсивних викликів, існують незалежно один від одного
Рекурсія досить широко застосовується в програмуванні, що засноване на рекурсивної природі багатьох математичних алгоритмів. А також Ви повинні знати, що будь-який рекурсивний алгоритм можна перетворити в еквівалентний ітеративний (тобто використовує циклічні конструкції).
У великих і складних програмах іноді доводиться замінювати рекурсию на ітерацію. Справа в тому, що рекурсія пов'язана з багаторазовими викликами процедур, а це дещо менш ефективно при виконанні в порівнянні з використанням циклів. Однак рекурсивні версії програм, як правило, набагато коротше і наочніше.
Доброю ілюстрацією механізму рекурсії є функція для обчислення факторіала натурального числа. Згадаймо, що факторіалом числа називається твір всіх натуральних чисел від 1 до цього числа включно:
N! = 1 * 2 * 3 *. * (N-2) * (N-1) * N 1! = 1 0! = 1
Спочатку покажемо зазвичай не рекурсивную функцію для обчислення факторіала, яка реалізує ітеративний алгоритм обчислення:
Function NonRecFact (N: integer). LongInt; Var i. integer; Res. LongInt; Begin Res: = 1; for i: = 1 to N do res: = Res * i; NonResFact: = Res; End;