алгоритмом ланцюжка рекурсивних викликів називається деревом рекурсивних викликів. Більш детальний розгляд призводить до необхідності обліку витрат як на організацію виклику функції і передачі параметрів, так і на повернення обчислених значень і передачу управління в точку виклику. p> Можна помітити, що деяка гілка дерева рекурсивних викликів обривається при досягненні такого значення переданого параметра, при якому функція може бути обчислена безпосередньо. Таким чином, рекурсія еквівалентна конструкції циклу, в якому кожен прохід є виконання рекурсивної функції із заданим параметром. p> Розглянемо приклад для функції обчислення факторіала: дерево рекурсії при обчисленні 5! (Малюнок 2)
В
малюнок 2
Дерево рекурсивних викликів може мати і більш складну структуру, якщо на кожному виклику породжується кілька звернень - фрагмент дерева рекурсій для чисел Фібоначчі представлений на малюнку 3: обчислення п'ятого числа Фібоначчі Fb (5).
В
малюнок 3
Згаданий аналіз практичної складності програм показує, що часто асимптотично більш складні ітеративні алгоритми, на практиці стають більш ефективними. Так, порівнюючи швидкість обчислення чисел Фібоначчі з допомогою итеративной і рекурсивної функції можна помітити, що ітеративна функція виконується майже В«миттєвоВ», не залежно від значення. При використанні ж рекурсивної функції вже при помітна затримка при обчисленні, а при великих результат з'являється вельми не скоро. Причина, як уже було сказано, криється в тому, що в теорії не врахована залежність часу роботи програми від кількості викликів вкладених підпрограм. Неефективність рекурсії проявляється в тому, що одні й ті ж обчислення проводяться багато разів. Особливо сильно це виявляється в методі, який був самим затребуваним при побудові теоретично швидких рекурсивних алгоритмів, - методі бінарного розбиття на незалежні підзадачі. Коли підзадачі незалежні, це часто призводить до неприпустимо великим затратам часу, оскільки одні й ті ж підзадачі починають вирішуватися по багато разів.
Обходити подібні ситуації дозволяє підхід, з Вестн як динамічне програмування [22]. Цей підхід для реалізації рекурсивних програм дає можливість отримувати ефективні та елегантні рішення для великого класу задач.
Технологія, звана висхідним динамічним програмуванням (Bottom-up dynamic programming) заснована на тому, що значення рекурсивної функції можна визначити, обчислюючи всі значення цієї функції, починаючи з найменшого, використовуючи на кожному кроці раніше обчислені значення для підрахунку поточного значення. Вона застосовна до будь-якого рекурсивному обчисленню за умови, що ми можемо дозволити собі зберігати всі раніше обчислені значення. Це в результаті дозволить зменшити тимчасову залежність з експоненціальною на лінійну!
Спадний динамічне програмування (top-down dynamic programming) - ще більш проста технологія. Вона дозволяє виконувати рек...
