Fibonacci rekurencyjnie i licznik wywołań

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

Definicję F(n) = F(n-1) + F(n-2) można przepisać wprost jako funkcję rekurencyjną. Jest czytelna, ale bardzo wolna: te same wyrazy liczy wiele razy. Licznik pokazuje, ile wywołań potrzeba dla F(20). Krokuj małe n (np. zmień na `fib(4)`) i obserwuj stos wywołań: funkcja woła samą siebie, a każde wywołanie ma własne `n`.

wywolania = 0


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


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

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