Rekurencja z zapamiętywaniem wyników

Ciąg Fibonacciego: iteracyjnie i rekurencyjnie - Algorytmy z podstawy programowej (Python)

Wystarczy zapamiętać policzone już wyrazy w słowniku, żeby każdy liczyć tylko raz. Ta technika to **spamiętywanie** (memoizacja) i jest pierwszym krokiem do programowania dynamicznego.

pamiec = {}
wywolania = 0


def fib(n):
    global wywolania
    wywolania += 1
    if n <= 2:
        return 1
    if n not in pamiec:
        pamiec[n] = fib(n - 1) + fib(n - 2)
    return pamiec[n]


print(fib(20))
print("wywołań:", wywolania)
print(fib(90))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy z podstawy programowej·Zaloguj się, aby zapisać postęp na koncie.