Python'da Özyineleme: Temel Durum, Küçültme ve Derinlik Sınırı

Özyineleme nedir ve ne zaman akla gelir

Özyinelemeli (recursive) fonksiyon, kendi kendini çağıran fonksiyondur. Fikir, büyük bir problemi aynı türden daha küçük bir probleme indirgemek ve bu indirgeme sonunda doğrudan cevaplanabilen bir noktaya ulaşmaktır. Matematikteki faktöriyel buna klasik örnektir: bir sayının faktöriyeli, o sayı ile bir eksiğinin faktöriyelinin çarpımıdır; en küçük değerde ise sonuç doğrudan bilinir.

Gerçek işlerde özyineleme, yapısı kendini tekrar eden verilerde doğal bir çözümdür. İç içe geçmiş listeleri düzleştirmek, bir klasör ağacındaki dosyaları gezmek, bir organizasyon şemasında bir yöneticiye bağlı herkesi bulmak, JSON gibi iç içe yapıları dolaşmak bunlardandır. Bu yapıların her biri aynı türden alt parçalar içerir; fonksiyon bir parçayı işler, alt parçalar için kendini çağırır.

Her özyinelemeli çözüm döngüyle de yazılabilir. Seçim, hangisinin problemi daha doğal anlattığına bağlıdır: yapı ağaç gibiyse özyineleme, düz bir tekrar söz konusuysa döngü genellikle daha sade ve daha güvenlidir.

İlk örnek: faktöriyel

Faktöriyel en çok verilen örnektir; çünkü özyinelemenin üç parçasını açıkça gösterir. Aşağıdaki kodda BIR, tam sayı bir değerini taşıyan bir sabittir.

def faktoriyel(sayi): if sayi <= BIR: return BIR return sayi * faktoriyel(sayi - BIR)

Fonksiyonun ilk satırı temel durumu tanımlar: sayı bire eşit ya da küçükse sonuç doğrudan bir'dir. Bu satır olmazsa fonksiyon kendi kendini sonsuza dek çağırır. İkinci satır küçültme ve birleştirmeyi yapar: sayıyı bir azaltarak kendini çağırır, dönen sonucu sayıyla çarpar.

Çağrılar yığına eklenir. faktoriyel çağrıldığında fonksiyon bir kez daha çağırır, o bir kez daha çağırır ve temel duruma ulaşana kadar bu böyle sürer. Temel durumda dönen değer geriye doğru yığılmış çağrılara tek tek iletilir ve her biri kendi çarpımını yaparak sonucu üst çağrıya verir. Bu geri dönüş zinciri, özyinelemeyi izlerken akılda tutulması gereken kısımdır.

Özyinelemeyi anlamanın pratik yolu, küçük bir girdiyle çağrıları kağıt üzerinde adım adım yazmaktır. Hangi çağrının hangisini beklediğini görmek, fikri kavramak için en hızlı yoldur.

İş örneği: iç içe yapıyı dolaşmak

Özyinelemenin gerçek gücü, derinliği önceden bilinmeyen yapılarda ortaya çıkar. Örneğin bir veri kaynağından iç içe listeler gelir: bazı öğeler tek değer, bazıları kendi içinde başka listeler barındırır. Döngüyle bunu yazmak, derinlik bilinmediğinden zordur; özyinelemeyle sade bir çözümdür:

def duzlestir(oge): if not isinstance(oge, list): return [oge] sonuc = [] for alt in oge: sonuc.extend(duzlestir(alt)) return sonuc

Temel durum: öğe liste değilse tek elemanlı bir liste olarak döndürülür. Aksi halde listenin her öğesi için fonksiyon kendini çağırır ve sonuçlar birleştirilir. Liste ne kadar derin olursa olsun kod aynı kalır.

Aynı kalıp bir klasör ağacı için de geçerlidir: bir klasörün içindeki her öğe dosyaysa işle, klasörse aynı işlevi onun için çağır. Organizasyon şeması, ürün kategori ağacı ve iç içe sözlük ya da JSON yapıları da bu desene girer. Ortak nokta, parçanın kendisinin de aynı türden olmasıdır.

Bir ayrıntı: özyinelemeli çözümü yazarken önce temel durumu, sonra küçültmeyi, en son birleştirmeyi yazın. Bu sıra, sonsuz döngüye düşme riskini baştan ortadan kaldırır.

Derinlik sınırı ve RecursionError

Python her çağrı için bellekte yer ayırdığından özyineleme derinliğine bir sınır koyar. Python belgelerine göre bu sınır, yorumlayıcı yığınının azami derinliğidir ve sonsuz özyinelemenin C yığınını taşırıp Python'u çökertmesini önler. Sınıra ulaşıldığında RecursionError oluşur.

Sınırı sys.getrecursionlimit() ile görür, sys.setrecursionlimit() ile değiştirebilirsiniz. Ancak belgeler, olabilecek en yüksek sınırın platforma bağlı olduğunu ve fazla yüksek bir sınırın çökmeye yol açabileceğini açıkça uyarır; bu yüzden değiştirmek dikkat gerektirir. Pratikte sınırı yükseltmek yerine çözümü yeniden düşünmek daha sağlıklıdır.

İki yol vardır. Birincisi, yinelemeyi döngüye çevirmek: toplama, sayma ya da düz bir tekrar söz konusuysa döngü hem hızlı hem güvenlidir. İkincisi, yapıyı açık bir yığın (liste) ile kendiniz yönetmek: ağaç dolaşımı derin olabiliyorsa, yapılacakları bir listede tutup while ile işlemek, çağrı yığınına bağımlılığı kaldırır.

Derinliğin çok büyüyebileceği veriyle çalışıyorsanız ilk baştan döngü ya da açık yığın düşünün.

Tekrar eden hesap, önbellek ve yaygın tuzaklar

Özyinelemenin gizli maliyeti, aynı alt problemin tekrar tekrar çözülmesidir. Fibonacci dizisi bunun klasik örneğidir: her çağrı iki alt çağrı yapar ve aynı değerler defalarca hesaplanır. Çağrı sayısı girdiyle çok hızlı büyür ve fonksiyon küçük sayılarda bile yavaşlar.

Çözüm, sonuçları saklamaktır. Python'un standart kütüphanesindeki functools modülünde bu iş için hazır bir önbellek dekoratörü vardır; bir fonksiyonu sarmalayıp aynı argümanla çağrıldığında önceki sonucu döndürür. Böylece özyinelemeli yapıyı koruyup tekrarlı hesabı ortadan kaldırabilirsiniz. Bunun işe yaraması için fonksiyonun aynı girdiye her zaman aynı sonucu vermesi gerekir.

Sık yapılan hatalar:

• Temel durumu unutmak ya da yanlış yazmak: fonksiyon sonlanmaz ve RecursionError ile durur.
• Problemi küçültmeyi unutmak: aynı argümanla kendini çağıran fonksiyon asla temel duruma ulaşmaz.
• Dönen değeri kullanmamak: alt çağrının sonucunu return etmeden bırakmak, üst çağrıda None sonucuna yol açar.
• Değiştirilebilir varsayılan argümanı çağrılar arasında paylaşmak: ara sonuç listesini varsayılan değer yapmak, çağrılar arasında birikime neden olur.
• Gereksiz özyinelemeyi seçmek: basit bir toplama ya da sayma için döngü daha okunaklıdır.

Hata ayıklarken fonksiyonun başına geçici bir yazdırma satırı ekleyip her çağrıda girdiyi ve girinti düzeyini göstermek, çağrı zincirini görünür kılar.

Bu beceriyi Mindset programlarında nerede çalışırsınız

Python ile Programlama Eğitimi Fonksiyonlar modülünü, Data Science Bootcamp Fonksiyonlar ve Veri Yapıları modüllerini içerir; özyineleme bu iki başlığın birleştiği, iç içe verilerle çalışırken en çok karşılaşılan tekniktir. Hiyerarşik verileri, kategori ağaçlarını ya da iç içe JSON yapılarını işleyen bir analist için özyinelemeyi tanımak, çözümü ilk denemede doğru kurmayı kolaylaştırır.