Zstępująco z zapamiętywaniem

Metoda zstępująca i wstępująca: rekurencja a iteracja - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Metoda **zstępująca** (top-down) zaczyna od problemu, który chcemy rozwiązać, i schodzi do mniejszych: to zwykła rekurencja. Gdy te same podproblemy powtarzają się (Fibonacci), wyniki warto **zapamiętać** w słowniku: każdą wartość liczy się wtedy tylko raz, a liczba wywołań spada z wykładniczej do liniowej.

memo = {}
calls = 0

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

print(fib(80), "wywołań:", calls)

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

Wszystkie lekcje kursu Informatyka - liceum klasa 2, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.