Recursive Fibonacci

Fibonacci'yi recursion ile hesaplayan fonksiyonu yazmayı öğrenirsin.

Taban durum

Fibonacci'de iki taban durum vardır: F(0) = 0 ve F(1) = 1. Bu iki değer doğrudan bilinir ve recursion'ı durdurur.

İki taban durum olması, fonksiyonun her zaman sonlanmasını sağlar. Çünkü her çağrı n'yi azaltır ve sonunda 0 veya 1'e ulaşır.

Naive recursive Fibonacci'nin karmaşıklığı O(2^n)'dir. Bu, her çağrının iki alt çağrı yapması nedeniyle üstel büyümedir.

n=40 için milyarlarca çağrı yapılır. Bu, naive recursion'ın neden yavaş olduğunu gösterir. Memoization bu sorunu çözer.

fib_small(n) yaz. n=0 ise 0, n=1 ise 1 döndür. print(fib_small(1)) ile 1 yazdır.

Örnek çözümü göster

def fib_small(n):
    # Küçük Fibonacci
    if n == 0:
        return 0
    if n == 1:
        return 1
print(fib_small(1))