Özyineleme ve Python'un Onu Neden (Sevmediği) 🌀

Mülakatta sizden faktöriyel veya Fibonacci sayılarını özyineleme ile yazmanızı isterlerse yazın. Ama gerçek hayatta sık kullanıyorsanız...
Evet, özyineleme kavramsal olarak güzel, matematiksel olarak zariftir, ancak aşırıya kaçarsanız prodüksiyonu çökertebilir ve tüm RAM'i yığın çerçeveleriyle doldurabilirsiniz.

Kaputun altında neler olduğunu ve Python'un neden fonksiyonel dillerin aksine özyinelemeyi pek sevmediğini inceliyoruz.

1️⃣ Maliyet: Çağrı yığını
Her fonksiyon çağrısı bedava değildir. Bellekte yeni bir yığın çerçevesi oluşturulur. Bu çerçevede yerel değişkenler ve dönüş adresi saklanır.
Her bir sonraki bebeğin bir öncekiyle aynı ağırlıkta olduğu bir iç içe geçmiş bebek düşünün. Python'da bu "ağırlık" RAM'e biner.
while veya for döngüsü tek bir bellek bloğu kullanır. Özyineleme, çağrı derinliğiyle orantılı olarak belleği doğrusal (veya üstel) şekilde tüketir.

2️⃣ Neden kuyruk optimizasyonu yok
Haskell veya C++ gibi dillerde derleyici akıllıdır. Özyinelemeli çağrı fonksiyondaki son işlemse (kuyruk özyinelemesi), onu sıradan bir atlamaya (GOTO) dönüştürür, yeni bir çerçeve oluşturmaz. Buna Tail Call Optimization (TCO) denir.

Python'da TCO yoktur ve olmayacaktır. Guido van Rossum (BDFL) prensip olarak Python'da TCO'ya karşıdır. Argümanı basit: "Hata izlerinin tamamını görmek istiyoruz." Yığını daraltırsanız, özyinelemenin hangi adımında hatanın oluştuğunu asla bilemezsiniz.
Bu nedenle varsayılan 1000 çağrı limiti bir hata değil, yığın taşmasına karşı bir korumadır. Bunu sys.setrecursionlimit ile artırabilir misiniz? Artırabilirsiniz. Ancak buna ihtiyacınız varsa, %99 olasılıkla mimaride hata yapmışsınızdır.

3️⃣ Özyineleme ne zaman kötü, ne zaman gereklidir?
❌ Doğrusal yapılar (örneğin listeler): Faktöriyel, Fibonacci sayıları veya düz bir listeyi dolaşma. Yinelemeli while/for döngüsü her zaman daha hızlı ve bellek açısından daha verimlidir (O(1) bellek vs O(N)).
✅ Dallanmış yapılar (ağaçlar, graflar, iç içe sözlükler): JSON ayrıştırma, dosya sistemi dolaşma, DOM ağacı veya Böl ve Fethet algoritmaları (QuickSort, MergeSort). Burada özyineleme bilişsel yükü azaltır ve kodu okunabilir kılar.

4️⃣ Yavaşlığa çare: @lru_cache
Klasik aptallık örneği, Fibonacci'yi "kaba kuvvet" ile hesaplamaktır. Karmaşıklık O(2^n). Bu, 50. sayıyı hesaplamak için programın bitirmeden önce öleceği anlamına gelir.
Çözüm — Ezberleme.
@functools.lru_cache dekoratörü, çağrı sonuçlarını önbelleğe alır. Fonksiyon aynı argümanla daha önce çağrıldıysa, Python hazır değeri karma tablosundan alır. Bu, üstel korkunçluğu doğrusal karmaşıklığa O(N) dönüştürür.

Özet: Python, Haskell veya Lisp değildir. Burada özyineleme ikinci sınıf bir vatandaştır. Ağaçlar ve graflar için kullanın, ancak diğer her şey için döngüler vardır.

#anatomi_piton