C Programlama #20 | Fibonacci: Özyineleme mi, Döngü mü? Üstel Büyüme

Eğitmen: Dr. Süleyman Burak ÇELİK

0, 1, 1, 2, 3, 5, 8: her sayı önceki ikisinin toplamı. Yirminci derste Fibonacci sayılarını kendini iki kez çağıran bir fonksiyonla hesaplıyor, çağrıların nasıl çığ gibi büyüdüğünü ölçüyor ve aynı işi döngüyle yazıp ikisini karşılaştırıyoruz. İkinci bloğun son dersi. Ardışık iki Fibonacci sayısının oranı altın orana (yaklaşık 1,618) yaklaşır. Özyinelemeli tanımın iki temel durumu (fib(0) = 0, fib(1) = 1) ve iki özyinelemeli çağrısı var; program 0'dan 10'a kadar 0 1 1 2 3 5 8 13 21 34 55 yazıyor. Her çağrıda adını içeri kaydırarak yazan bir sürümle fib(4)'ün çağrı ağacını çıkarıyoruz: 9 çağrı, sonuç 3; ama fib(2) iki, fib(1) üç kez hesaplanıyor. Ağaçta önce soldaki çağrı hesaplandı; bu bir kural değil: C, + işlecinin iki tarafının ve fonksiyon argümanlarının hesaplanma sırasını belirlemez. Aynı program bu Mac'te (gcc-16 ve clang) önce birinci argümanı, Linux sunucumuzda (gcc 11) önce ikinci argümanı hesaplıyor. Bir sayaçla çağrıları sayıyoruz: fib(10) 177, fib(20) 21 891, fib(30) 2 692 537, fib(40) 331 160 281 çağrı; her 10 adımda yaklaşık 123 kat, yani altın oranın onuncu kuvveti: üstel karmaşıklık. Özyinelemeli fib(40) yaklaşık 0,3 saniye sürüyor; iki değişkenli döngü ise 39 turda aynı sonucu (102 334 155) 0,002 saniyede buluyor. İlk üç turu lldb ile gerçek değerleriyle izliyor, son olarak özyineleme ile döngünün ortak yanlarını ve özyinelemenin bedelini karşılaştırıyoruz. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Fibonacci dizisi ve altın oran 2. İki temel durum, iki özyinelemeli çağrı; fib(4)'ün çağrı ağacı 3. Hesaplama sırası belirsiz: aynı program Mac'te soldan, Linux'ta sağdan 4. Çağrı sayısı üstel büyür: fib(40) için 331 milyondan fazla çağrı 5. Aynı iş döngüyle: 39 tur, yüz kattan fazla hızlı Bölümler: 0:00 Fibonacci: özyineleme mi, döngü mü? 0:19 Her sayı, önceki ikisinin toplamı 0:49 İki temel durum, iki çağrı 1:23 fib(4)'ün çağrı ağacı 2:06 Hangisi önce hesaplanır? 2:57 Kaç çağrı? Üstel büyüme 3:43 Aynı iş döngüyle 4:21 Özyineleme mi, döngü mü? 4:58 Bugünün dört kuralı 5:24 2. blok bitti; sırada diziler Kaynak kitap: Paul Deitel, Harvey Deitel — C How to Program, 9. baskı (2022), §5.15–5.16. Konu sırası ve kavramlar kaynak kitaptan izlenir; anlatım, örnekler ve ekranlar özgündür. Hedef kitle: C'ye yeni başlayan tüm mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: C Programlama #01–#19.

Bu videoyu izlemek için Premium üyelik gerekir.