Recursivitatea fără memoizare rulează la nesfârșit: fib(40) nu se mai termină
Funcția recursivă recalculează aceleași subprobleme de un număr exponențial de ori (fib(40) face sute de milioane de apeluri), așa că pare blocată și editorul o oprește după limita de timp. Salvează rezultatele: @lru_cache(maxsize=None) sau un dicționar memo.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Recursivitatea fib(n) = fib(n - 1) + fib(n - 2) e corectă, dar fiecare apel pornește alte două, iar aceleași valori sunt calculate din nou și din nou: fib(38) de 2 ori, fib(37) de 3 ori, fib(36) de 5 ori, și tot așa. Numărul total de apeluri crește aproape ca 1,6 la puterea n: pentru fib(40) sunt peste 300 de milioane de apeluri.
Nu primești nicio excepție (adâncimea e doar 40, deci nu e RecursionError), doar programul nu se termină în timp util. În editorul nostru e oprit după limita de timp, cu „Programul a rulat prea mult și a fost oprit”.
Aceasta este exact situația pentru care există programarea dinamică: subprobleme care se repetă. Reparația minimă e memoizarea: ții minte rezultatul fiecărui fib(k) după primul calcul. Cu functools.lru_cache sau un dicționar, fiecare valoare se calculează o singură dată, iar complexitatea scade de la exponențială la O(n).
De ce apare: cauzele frecvente
1Subprobleme recalculate
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(40))from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(40))lru_cache salvează rezultatul pentru fiecare n. Al doilea apel cu același n întoarce imediat valoarea salvată.
2Memo creat, dar necitit
memo = {}
def drumuri(r, c):
if r == 0 or c == 0:
return 1
memo[(r, c)] = drumuri(r - 1, c) + drumuri(r, c - 1)
return memo[(r, c)]memo = {}
def drumuri(r, c):
if r == 0 or c == 0:
return 1
if (r, c) in memo:
return memo[(r, c)]
memo[(r, c)] = drumuri(r - 1, c) + drumuri(r, c - 1)
return memo[(r, c)]Salvarea fără verificarea de la început nu ajută: fiecare apel recalculează tot. Verificarea if (r, c) in memo trebuie să fie înaintea apelurilor recursive.
3Varianta iterativă (tabelară)
print(fib(40)) # varianta recursivă simplădef fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib(40))Calculul de jos în sus folosește doar ultimele două valori: timp O(n), memorie O(1), fără recursivitate.
Repară eroarea, direct în pagină
Funcția moduri(n) numără în câte moduri poți urca o scară cu n trepte, făcând pași de 1 sau 2 trepte. E corectă, dar pentru n = 40 nu se termină și e oprită după limita de timp. Fă-o rapidă, ca programul să afișeze 8, 1 și 165580141.
def moduri(n):
if n <= 1:
return 1
return moduri(n - 1) + moduri(n - 2)
print(moduri(5))
print(moduri(0))
print(moduri(40))8 1 165580141
Indiciu
Ține minte rezultatul pentru fiecare n, de exemplu cu @lru_cache(maxsize=None) din functools.
Reparația
from functools import lru_cache
@lru_cache(maxsize=None)
def moduri(n):
if n <= 1:
return 1
return moduri(n - 1) + moduri(n - 2)
print(moduri(5))
print(moduri(0))
print(moduri(40))De ce merge
Ca să ajungi pe treapta n, ultimul pas a fost de pe n - 1 sau de pe n - 2, deci moduri(n) = moduri(n - 1) + moduri(n - 2). Fără memoizare, aceleași valori erau recalculate de un număr exponențial de ori: sute de milioane de apeluri pentru n = 40. Cu @lru_cache(maxsize=None), fiecare moduri(k) se calculează o singură dată, deci sunt doar 41 de calcule distincte: timp O(n).
Alte forme ale mesajului
Programul a rulat prea mult și a fost oprit. Verifică dacă ai o buclă infinită.
Cum o eviți pe viitor
Când scrii o recursivitate cu mai multe apeluri pe aceeași ramură (f(n - 1) + f(n - 2), f(i + 1, j) + f(i, j + 1)), întreabă-te dacă aceeași combinație de argumente poate apărea de mai multe ori. Dacă da, adaugă @lru_cache(maxsize=None) sau un memo, verificat la începutul funcției. Testează cu o valoare mare (n = 40, grilă 15×15) înainte să consideri soluția gata.
Întrebări frecvente
De ce fib(30) merge, iar fib(40) nu?
Pentru că numărul de apeluri crește exponențial: fiecare +1 la n înmulțește munca cu aproximativ 1,6. De la 30 la 40 munca crește de peste 100 de ori.
lru_cache sau dicționar memo?
lru_cache e mai scurt și mai greu de greșit. Dicționarul e util când vrei să vezi sau să golești memo-ul, sau când argumentele sunt liste (care nu pot fi folosite de lru_cache).
Erori înrudite
TypeError: unhashable type: 'list' cu @lru_cache @lru_cache folosește argumentele funcției ca cheie de dicționar, iar o listă nu poate fi cheie. Transmite un tuplu (tuple(lista)) sau, mai bine, păstrează lista în afara funcției memoizate și trimite doar indici. Memo greșit: cheia nu conține toți parametrii, iar rezultatul e greșit Ai salvat în memo rezultatul doar după i (memo[i]), dar funcția depinde și de alt parametru (capacitate, j, suma rămasă), așa că un rezultat calculat pentru o stare e refolosit pentru alta. Cheia memo-ului trebuie să conțină toți parametrii care schimbă rezultatul: memo[(i, capacitate)]. RecursionError: maximum recursion depth exceeded Funcția recursivă s-a apelat de prea multe ori fără să se oprească, iar Python a depășit limita de aproximativ 1000 de apeluri imbricate. Adaugă un caz de bază (de exemplu if n <= 1: return 1) și verifică dacă fiecare apel se apropie de el. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
