Özyineleme (Recursion) Nedir? Fonksiyonların Kendisini Çağırması

Özyineleme, tek somut bir örnek görene kadar döngüsel görünen, sonra her şeyin yerine oturduğu kavramlardan biridir. Fikir şudur: bir fonksiyon, aynı problemin daha küçük bir sürümünü çözerek sorunu çözer ve problem doğrudan yanıtlanacak kadar küçülene dek bunu tekrarlar.

Her özyinelemeli fonksiyonun karşılaması gereken iki kural

1. Temel durum: fonksiyonun kendisini çağırmadan doğrudan sonuç döndürdüğü en az bir girdi olmalıdır. Bu olmadan fonksiyon sonsuza dek çalışır.
2. Özyinelemeli durum: her özyinelemeli çağrı temel duruma yaklaşmalıdır; problem küçülmelidir. Küçülmüyorsa sonsuz özyineleme var demektir.

Klasik örnek: faktöriyel

faktöriyel(n) = n · faktöriyel(n−1), faktöriyel(0) = 1 koşuluyla. Kodda: function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); }. factorial(4) çağrısı şu zinciri oluşturur: 4 · factorial(3) = 4 · 3 · factorial(2) = 4 · 3 · 2 · factorial(1) = 4 · 3 · 2 · 1 · factorial(0) = 24.

Çağrı yığını gerçekte nasıl görünür

Her fonksiyon çağrısı, çağrı yığınında o çağrıya ait yerel değişkenleri ve dönüş adresini tutan yeni bir çerçeve oluşturur. factorial(4) için dört çerçeve üst üste yığılır. factorial(0) bir döndürdüğünde, çalışma zamanı çarparak çerçeveleri teker teker patlatır. Yığın taşması, herhangi bir dönüş gerçekleşmeden önce çok fazla çerçeve birikmesiyle olur — sonsuz özyinelemenin programı çökertmesinin nedeni budur.

Ağaç özyinelemesi: Fibonacci

fib(n) = fib(n−1) + fib(n−2), fib(0) = 0 ve fib(1) = 1 ile. Bu ağaç özyinelemesidir — her çağrı iki tane daha üretir. fib(5), 15 fonksiyon çağrısıyla bir ağaç oluşturur. fib(40) için bir milyarın üzerinde çağrı gerekir. Çözüm memoizasyon: her sonucu ilk hesaplandığında önbelleğe al; özyinelemeden önce önbelleği kontrol et.

Memoize edilmiş Fibonacci

function fib(n, memo = {}) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; }. Artık fib(40) bir milyar yerine yalnızca 79 çağrı yapar. Memo nesnesi üstel zamanı doğrusal zamana dönüştürür.

Özyineleme bir döngünün yerini aldığında

Özyineleme, veri doğal olarak ağaç biçimindeyken parlar: dosya sistemi gezme, JSON ayrıştırma, ağaç veya çizge algoritmaları. Düz bir diziyi dolaşmak doğal olarak döngüseldir; iç içe geçmiş bir yapıyı dolaşmak doğal olarak özyinelemlidir. Ağaç problemine döngü uygulamak kendi açık yığınını yönetmeyi gerektirir — bu da dili kullandığında tam olarak yaptığı şeydir.

Özyinelemeli bir çağrı ağacını elle izlemek, kavramı otomatik hale getirir. Özyinelemeli bir fonksiyonu Solvequill'e yapıştır; açıklama videosu çağrı ağacını çizer, her dönüş değerinin nasıl geriye aktarıldığını gösterir ve temel durumu açıkça adlandırır.