Fibonacci: de la exponențial la liniar
Șirul lui Fibonacci (0, 1, 1, 2, 3, 5, 8, ...) are o definiție recursivă perfectă: fiecare termen este suma celor doi dinainte. Scrisă direct, funcția este însă exponențială: pentru n = 50 nu s-ar termina în viața ta. Cu memoizare (ții minte rezultatele deja calculate) devine O(n). Este prima ta întâlnire cu programarea dinamică.
Varianta naivă
fib(0) = 0, fib(1) = 1, iar fib(n) = fib(n - 1) + fib(n - 2). Codul copiază exact definiția:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print([fib(i) for i in range(10)]) Scrie fib_numarat(n), care returnează numărul de apeluri făcute de varianta naivă pentru fib(n), și fib_memo(n), varianta cu memoizare (dicționar sau lru_cache). Funcția naivă primește un contor ca listă [0], ca să poată fi modificat din to…
- În fib_naiv(n, contor), mărește contor[0] la fiecare apel și calculează recursiv.
- fib_numarat(n) creează contor = [0], apelează fib_naiv și returnează contor[0].
- fib_memo(n) cu @lru_cache(maxsize=None) sau cu un dicționar. Trebuie să apară: 177, 21891, 12586269025, 2880067194370816120.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan