Bəzi rekursiv alqoritmlər eyni alt-məsələni dəfələrlə həll edir. Bu üst-üstə düşən alt-məsələlər adlanır. Memoizasiya hər alt-məsələnin cavabını ilk dəfə hesablayanda yadda saxlayır, sonra isə hazır nəticəni qaytarır. Beləliklə eksponensial vaxt çox vaxt polinomiala düşür.

`fib(5)` çağırış ağacı: 15 çağırış və təkrarlar, keşlə isə 6 qiymət
fib(5) çağırış ağacı: 15 çağırış və təkrarlar, keşlə isə 6 qiymət

Fibonacci: eksponensial partlayış

fib(n) fib(n-1) və fib(n-2)-ni çağırır, onların hər biri isə yenidən eyni şeyi edir. Məsələn fib(3) fib(5) ağacında iki dəfə hesablanır. Çağırışların sayı təxminən 1.618^n artır.

python
calls = 0

def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

for n in (10, 20, 25):
    calls = 0
    fib(n)
    print(n, calls)
text
10 177
20 21891
25 242785

Əllə memoizasiya: lüğət

Ən sadə üsul: nəticələri dict-də saxlayın. Funksiya əvvəlcə n in memo yoxlayır, tapılsa dərhal qaytarır, yoxsa hesablayıb yazır. İndi hər n üçün yalnız bir dəfə hesablanır.

python
calls = 0
memo = {}

def fib(n):
    global calls
    calls += 1
    if n in memo:
        return memo[n]
    memo[n] = n if n < 2 else fib(n - 1) + fib(n - 2)
    return memo[n]