...
Eroare Algoritmi și structuri de date · Programare dinamică și memoizare

Recursivitatea fără memoizare rulează la nesfârșit: fib(40) nu se mai termină

Pe scurt

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

Greșit
PYTHON
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(40))
Corect
PYTHON
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

Greșit
PYTHON
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)]
Corect
PYTHON
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ă)

Greșit
PYTHON
print(fib(40))  # varianta recursivă simplă
Corect
PYTHON
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ă tu

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.

Codul care dă eroarea
PYTHON
def moduri(n):
    if n <= 1:
        return 1
    return moduri(n - 1) + moduri(n - 2)

print(moduri(5))
print(moduri(0))
print(moduri(40))
După reparație, programul afișează
8
1
165580141
Indiciu

Ține minte rezultatul pentru fiecare n, de exemplu cu @lru_cache(maxsize=None) din functools.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.