перше обчислення fib(k)повторне обчисленняузято з пам'ятіпоточний виклик
Дерево викликів
Ріст кількості викликів
наївна: 2·fib(n+1) − 1мемоізація: 2n − 1
Як рахує модель
fib(0) = 0, fib(1) = 1 – база, далі fib(n) = fib(n−1) + fib(n−2).
Наївна рекурсія: викликів C(n) = C(n−1) + C(n−2) + 1, звідси C(n) = 2·fib(n+1) − 1 ≈ 1,6n – експонента.
Мемоізація: перед обчисленням дивимось у словник memo. Кожне fib(k) рахується один раз, тож викликів 2n − 1 – лінійно.
Дерево будується в тому порядку, у якому виконується програма: спершу вся ліва гілка fib(n−1), потім права.
Що спробувати
- Для n = 6 порахуйте, скільки разів обчислюється fib(2) у наївному дереві. Знайдіть закономірність: це теж число Фібоначчі!
- Збільшуйте n на 1 і стежте за лічильником: у скільки разів зростає кількість викликів? До якого числа прямує відношення?
- Перемкніться на мемоізацію: чому права гілка кожного вузла стала одним сірим листком?
- За таблицею оцініть: якщо комп'ютер робить мільярд викликів за секунду, скільки чекати наївного fib(50)?
- Придумайте, як порахувати fib(n) взагалі без рекурсії, лише двома змінними.
Чому так?
Наївна рекурсія не пам'ятає результатів: щоб знайти fib(n−1), вона заново рахує fib(n−2), хоча його доведеться рахувати й у сусідній гілці. Повторні гілки (червоні) займають більшу частину дерева, і з кожним n дерево стає майже в 1,6 раза більшим.
Мемоізація – найпростіша форма динамічного програмування: «розв'язав підзадачу – запиши відповідь». Пам'ять O(n) обмінюємо на час: замість мільйонів викликів – десятки.
Шкільна програма: інформатика, 9–11 клас (рекурсія, складність алгоритмів, динамічне програмування).