нням послідовності та обчислення n-го елемента є насправді багаторазове взяття функції f від самої себе:
В
Зокрема для факторіала можна написати:
Factorial (n: integer): integer; n> 1 then: = n * Factorial (n-1): = 1;;
Слід розуміти, що виклик функцій тягне за собою деякі додаткові накладні витрати, тому перший варіант обчислення факторіала буде кілька більш швидким. Взагалі ітераційні рішення працюють швидше рекурсивних. Перш ніж переходити до ситуацій, коли рекурсія корисна, звернемо увагу ще на один приклад, де її використовувати не слід. Розглянемо окремий випадок рекурентних співвідношень, коли таке значення в послідовності залежить не від одного, а відразу від кількох попередніх значень. Прикладом може служити відома послідовність Фібоначчі, в якій кожен наступний елемент є сума двох попередніх:
В
При В«лобовомуВ» підході можна написати:
Fib (n: integer): integer; n> 1 then: = Fib (n-1) + Fib (n-2)
else: = 1;;
Кожен виклик Fib створює одразу дві копії себе, кожна з копій - ще дві і т.д. Кількість операцій зростає з номером n експоненціально, хоча при ітераційному вирішенні досить лінійного по n кількості операцій. p> Насправді, наведений приклад вчить нас не КОЛИ рекурсію не слід використовувати, а тому ЯК її не слід використовувати. Зрештою, якщо існує швидке ітераційне (на базі циклів) рішення, то той же цикл можна реалізувати за допомогою рекурсивної процедури або функції. Наприклад:
// x1, x2 - початкові умови (1, 1)
// n - номер необхідного числа Фібоначчі
function Fib (x1, x2, n: integer): integer;
var: integer; n> 1 then: = x2 + x1;: = x2;: = x3;: = Fib (x1, x2, n-1); else: = x2;;
І все ж ітераційні рішення переважні. Питається, коли ж у такому разі, слід користуватися рекурсією? p> Будь рекурсивні процедури і функції, що містять всього один рекурсивний виклик самих себе, легко замінюються ітераційними циклами. Щоб отримати щось, що не має простого нерекурсівние аналога, слід звернутися до процедур і функцій, що викликає себе два і більше разів. У цьому випадку безліч викликаються процедур утворює вже не ланцюжок, як на рис. 1, а ціле дерево. Існують широкі класи задач, коли обчислювальний процес повинен бути організований саме таким чином. Якраз для них рекурсія буде найбільш простим і природним способом вирішення. br/>
. Дерева
Теоретичною базою для рекурсивних функцій, що викликають себе більше одного разу, служить розділ дискретної математики, що вивчає дерева.
.1 Основні визначення. Способи зображення дерев
Визначення: Деревом будемо називати кінцеве безліч T, що складається з одного або більше вузлів, таких що:
а) Є один спеціальний вузол, званий коренем даного дерева.
б) Інші вузли (виключаючи корінь) містяться в попарно непересічних підмножинах, кожне з яких у свою чергу є деревом. Дерева...
