9. SınıfBilişim Teknolojileri
Özyineleme ve Çözümleme — Çalışma Sayfası
Kazanımlar, önemli noktalar ve sık yapılan hatalar tek sayfada.
Bu konuda öğrenecekleriniz
- Özyinelemeli çözüm kurar ve temel durum koşulunu doğru belirler.
- Özyineleme ile döngü arasındaki benzerliği ve farkı açıklar.
- Çağrı yığınının nasıl büyüdüğünü ve neden taşabildiğini anlatır.
- Ağaç yapılarında ve böl ve birleştir yaklaşımında özyinelemeyi uygular.
- Özyinelemeli çözümün verimsizlik nedenlerini tespit edip yolunu düzeltir.
Önemli noktalar
- Özyineleme, bir fonksiyonun kendisini çağırmasıdır.
- Temel durum koşulu olmadan özyineleme hiçbir zaman durmaz.
- Her çağrıda girdi küçülmelidir; küçülmezse koşul sağlanmaz.
- Temel durum doğrudan sonuç döndürür, kendini çağırmaz.
- Çağrı yığını her çağrıda büyür ve dönüşlerde küçülür.
- Sonsuz özyineleme yığın taşmasına ve programın kapanmasına yol açar.
- Ağaç ve klasör yapılarında gezinme özyinelemenin doğal alanıdır.
- Alt problemin sonucu birleştirilerek üst çağrıya döndürülmelidir.
- Tekrarlı hesaplarda saklama tablosu kullanmak hesap sayısını azaltır.
Formüller ve kurallar
- Temel durum: girdi indirgenemeyecek kadar küçüldüğünde doğrudan döndürülen sonuçtur.
- İndirgeme kuralı: her çağrıda girdi bir alt değere ya da daha küçük bir parçaya indirgenir.
- Beş et faktöriyelinin değeri 1 × 2 × 3 × 4 × 5, yani 120'dir.
- Fibonacci dizisinin ilk altı teriminin toplamı 1 + 1 + 2 + 3 + 5 + 8, yani 20'dir.
- Dört terimli toplamın çağrı yığını derinliği, terim sayısının bir fazlasıdır.
- Disk sayısı n olan Hanoi probleminde hamle sayısı 2^n eksi 1 formülüyle bulunur.
- Üç diskli Hanoi probleminde hamle sayısı 2³ eksi 1, yani 7'dir.
- Beş diskli Hanoi probleminde hamle sayısı 2⁵ eksi 1, yani 31'dir.
- Sekiz elemanlı dizinin ilk bölme adımında parça eleman sayısı 8 / 2, yani 4 olur.
Sık yapılan hatalar
- Temel durum koşulunu yazmamak: Çağrı zinciri hiç bitmez. Doğrusu durma noktasını açıkça tanımlamaktır.
- Çağrıda girdiyi küçültmemek: Aynı girdiyle çağrı tekrarlanır. Doğrusu daha küçük bir girdi vermektir.
- Temel durumda da kendini çağırmak: Durma koşulu çalışmaz. Doğrusu temel durumda doğrudan sonuç döndürmektir.
- Alt problemin sonucunu döndürmemek: Üst çağrıda sonuç eksik kalır. Doğrusu dönen değeri birleştirmektir.
- Tekrarlı hesaplarda saklama kullanmamak: Hesap sayısı hızla büyür. Doğrusu hesaplanan alt sonuçları saklamaktır.
- Yığın taşmasını bellek arızası sanmak: Kök neden yanlış belirlenir. Doğrusu koşulların sağlanıp sağlanmadığını denetlemektir.
- Her problemi özyineleme ile çözmek: Kod gereksiz uzar. Doğrusu döngü yeterliyse döngüyü seçmektir.
- Ağaç gezinmesinde dönüş noktasını atlamak: Diğer dallar taranmaz. Doğrusu kaldığı yeri hatırlamaktır.
Hızlı tekrar ipuçları
- Özyinelemeli bir çözüm yazmadan önce temel durumu bir satır olarak yazın; sorunun yarısı çözülmüş olur.
- Çağrı satırındaki güncellemeyi ayrı bir cümleyle yazın ve girdinin gerçekten küçüldüğünü doğrulayın.
- Küçük bir diziyle çağrı yığını derinliğini elle sayarak alışkanlık edin.
- Ağaç gezinmesinde dönüş noktasını kâğıda çizmeden koda geçmeyin.
- Tekrarlı hesap yapılan problemlerde önce saklama tablosunu değerlendirin.
- Derin özyinelemeden kaçınmak için girdiyi ikiye bölerek küçültmeyi düşünün.
Kendini dene
Bu sayfayı okuduktan sonra konu anlatımını tekrar oku ve kendi cümlelerinle özetle.