Recursive Fibonacci
- Algoritmalar kursu
- Başlangıç
- Ders 42/80
- 4 dk
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.
Karmaşıklık
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.
Uygulama Küçük Fibonacci
fib_small(n) yaz. n=0 ise 0, n=1 ise 1 döndür. print(fib_small(1)) ile 1 yazdır.
Başlangıç kodu
def fib_small(n):
# Küçük FibonacciÖrnek çözüm
def fib_small(n):
# Küçük Fibonacci
if n == 0:
return 0
if n == 1:
return 1
print(fib_small(1))Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 İkinci taban
F(1) = ____F(1) = 1Açıklama: 1 doğru.
2 Recursive Fibonacci: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
F(0)=0 |
Taban |
F(1)=1 |
İkinci taban |
O(2^n) |
Naive |
Çift çağrı |
Üstel |
3 Naive recursive Fibonacci'nin karmaşıklığı nedir?
- O(log n)
- O(n^2)
- O(2^n) Doğru cevap
- O(n)
Açıklama: O(2^n) üstel büyümedir.