Fibonacci dizisi

Her sayının önceki iki sayının toplamı olduğu Fibonacci dizisini öğrenirsin.

Fibonacci dizisi, her sayının önceki iki sayının toplamı olduğu bir dizidir: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

İlk iki sayı 0 ve 1'dir. Sonraki her sayı F(n) = F(n-1) + F(n-2) formülüyle hesaplanır.

Recursive tanım

Fibonacci'nin recursive tanımı: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Bu doğrudan koda çevrilebilir.

Ancak bu naive recursive çözüm çok yavaştır çünkü aynı alt problem defalarca hesaplanır.

fib(n) yaz. n < 2 ise n döndür, değilse fib(n-1) + fib(n-2). print(fib(6)) ile 8 yazdır.

Örnek çözümü göster

def fib(n):
    # Fibonacci hesapla
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
print(fib(6))