Özyinelemeli Fonksiyon Nasıl Çalışır? Base Case ve Call Stack Örneği

Özyinelemeli fonksiyon nasıl çalışır? Fonksiyon, problemi daha küçük bir alt probleme dönüştürüp kendisini yeni girdiyle yeniden çağırır. Base case olarak adlandırılan durma koşuluna ulaşıldığında yeni çağrı yapılmaz ve call stack'te bekleyen çağrılar, son çağrıdan ilk çağrıya doğru çözülür.

Bunu iki yönlü bir şema gibi düşünebilirsin: aşağı inerken f(n) çağrısı f(n - 1) gibi daha küçük bir çağrı kurar, yukarı çıkarken her bekleyen çağrı kendi işlemini tamamlayıp sonucunu bir üst çağrıya verir.

Özyinelemeli fonksiyon nasıl çalışır?

Özyineleme, bir fonksiyonun kendi gövdesi içinden kendisini çağırmasıdır. Ancak yalnızca kendisini çağırmak yeterli değildir. Her yeni çağrı, aynı problemin daha küçük veya çözülebilir bir hâline ilerlemelidir. Böylece çağrı zinciri aşağı doğru büyür, sonuçlar ise yukarı doğru birleşir.

Faktöriyel hesabı bu akışı görmek için kısa ve anlaşılır bir örnektir:

def faktoriyel(n):
    if n == 0:
        return 1
    return n * faktoriyel(n - 1)

print(faktoriyel(4))

faktoriyel(4) çağrısında base case, faktoriyel(0) çağrısıdır. Dört çağrı seviyesi, girdi, sonraki çağrı ve dönüş değeri bakımından şöyle izlenebilir:

faktoriyel(0) doğrudan 1 döndürür. Ardından bekleyen çarpımlar tamamlanır ve programın çıktısı şu olur:

24

Base case, recursive case ve çağrı çerçevesi nasıl ayrılır?

Base case, problemin doğrudan çözülebildiği ve yeni bir fonksiyon çağrısına ihtiyaç duyulmayan durma koşuludur. Bu dal, özyinelemenin nerede duracağını belirler.

Recursive case ise henüz doğrudan çözülemeyen girdiyi dönüştürür, problemi küçültür ve yeni bir çağrı kurar. Genel bir akış f(n) = işlem(n, f(n - 1)) biçiminde düşünülebilir. Burada f(n - 1) alt problemi çözer; dıştaki işlem, bu çağrıdan sonuç döndükten sonra tamamlanır.

Her fonksiyon çağrısı için oluşturulan çağrı çerçevesi, o çalıştırmaya ait geçici bilgileri taşır. Bu bilgiler arasında parametrenin değeri, yerel değişkenlerin mevcut durumu, alt çağrı tamamlandıktan sonra yapılacak bekleyen işlem ve fonksiyonun döneceği nokta bulunur.

Fonksiyon kendisini çağırdığında yeni çağrı çerçevesi call stack'e eklenir. Bu yapı son giren ilk çıkar düzeniyle çalışır. Örneğin f(3) çağrısı f(2) sonucunu bekliyorsa, f(3) çerçevesi stack üzerinde tutulur. f(2) tamamlanınca sonucu f(3)'e döner ve bekleyen işlem devam eder.

Bu nedenle bir özyinelemeli fonksiyonu incelerken iki noktayı birlikte takip etmek gerekir: Recursive case girdiyi base case'e yaklaştırıyor mu ve her çağrı, dönüş sonrasında hangi işlemi tamamlayacak?

4! örneğinde call stack ve dönüş sırası

faktoriyel(4) çağrısı sonucu hemen hesaplanmaz. Fonksiyon önce daha küçük girdilerle yeni çağrılar oluşturur. n değeri 1 olduğunda taban koşulu çalışır ve 1 döner. Bu noktadan sonra bekleyen çarpımlar, çağrıların ters yönünde tamamlanır.

def faktoriyel(n):
    if n == 1:
        return 1
    return n * faktoriyel(n - 1)

print(faktoriyel(4))

Beklenen çıktı:

24

n değeri 4, 3 ve 2 olduğunda recursive case çalışır. Her çağrı, mevcut sayıyı bir sonraki çağrıdan beklenen sonuçla çarpmak üzere saklar. n değeri 1 olduğunda yeni çağrı yapılmaz.

Call stack aşağı doğru kurulurken çağrı sırası şöyledir: faktoriyel(4), faktoriyel(3), faktoriyel(2) ve faktoriyel(1). En üstteki çağrı önce tamamlanır. faktoriyel(1) sonucu 1 döndürünce, bekleyen 2 * 1 işlemi 2 sonucunu üretir. Ardından 3 * 2 işlemi 6, son olarak 4 * 6 işlemi 24 sonucunu verir. Bu nedenle çağrıların kurulma yönü aşağı doğru, sonuçların çözülme yönü yukarı doğrudur.

Base case yoksa veya problem küçülmezse neden sonlanmaz?

Bir özyinelemeli fonksiyonun sonlanması için çağrı zincirinin bir noktada durma koşuluna ulaşması gerekir. Ayrıca recursive case, problemi bu koşula yaklaştırmalıdır. Bu iki şarttan biri bozulduğunda çağrılar dönüş alamadan büyümeye devam eder.

Durma koşulu hiç yazılmadığında

Fonksiyon her adımda f(n - 1) çağrısını yapıyor, fakat hiçbir koşul değer döndürmüyorsa zincir tabana ulaşamaz. Örneğin girdi dizisi f(3) → f(2) → f(1) → f(0) → f(-1) şeklinde sürer. Her çağrı, kendisinden sonra gelen çağrının sonucunu beklediği için üstteki çağrılar da tamamlanamaz.

Base case bulunsa bile ona ulaşılamadığında

Kodda n == 1 koşulu bulunması tek başına yeterli değildir. Fonksiyon f(0) ile başlarsa sonraki girdiler 0, -1, -2 şeklinde ilerler ve hiçbir zaman 1 değerine ulaşmaz. Benzer biçimde, sonraki çağrı aynı girdiyi koruyorsa zincir f(n) → f(n) → f(n) olarak kalır; problem küçülmediği için durma koşuluna yaklaşılmaz.

Teşhis için çağrı zincirindeki girdileri sırayla yaz. Her adımda girdinin değişip değişmediğini, değişiyorsa durma koşuluna yaklaşıp yaklaşmadığını ve farklı dalların aynı koşulu izleyip izlemediğini kontrol et. Çocuk çağrıdan dönüş gelmediğinde bekleyen çağrı çerçevelerindeki çarpma veya birleştirme işlemleri tamamlanamaz. Çağrı zinciri büyümeyi sürdürürse çalışma zamanı bir sınırla karşılaşıp işlemi durdurabilir.

Kendi özyineleme kodunu üçlü teşhis çerçevesiyle incele

Bir özyineleme kodunu incelerken yalnızca son çıktıya bakmak yerine çağrı zincirini satır satır kaydetmek daha açıklayıcı bir yöntemdir. Her satırda üç alanı doldur: girdi, bir sonraki çağrı ve dönüş değeri. Önce çağrı zincirini aşağı doğru, ardından değerlerin nasıl geri taşındığını yukarı doğru yaz. İlk eksik veya tutarsız kayıt, hatanın hangi aşamada oluştuğunu bulmana yardımcı olur.

Örneğin topla(n) fonksiyonunun n + topla(n - 1) mantığıyla çalıştığını ve n = 0 durumunda 0 döndürdüğünü düşün. Kayıtları şöyle tutabilirsin:

• Girdi: 3, bir sonraki çağrı: topla(2), dönüş değeri: 6
• Girdi: 2, bir sonraki çağrı: topla(1), dönüş değeri: 3
• Girdi: 1, bir sonraki çağrı: topla(0), dönüş değeri: 1
• Girdi: 0, bir sonraki çağrı: yok, dönüş değeri: 0

Bu kayıt yöntemiyle aşağıdaki üç soruyu sırayla sorarak kodun hangi bölümünü kontrol edeceğini belirleyebilirsin:

1. Problem küçülüyor mu? Özyinelemeli çağrının girdisini veya alt problemini kontrol et. n - 1 gibi bir değişim, çağrının daha küçük bir probleme ilerleyip ilerlemediğini gösterir.
2. Durma koşulu var mı? Taban durumu kontrol eden koşula bak. Bu koşulun çağrı zinciri tarafından gerçekten ulaşılabilir olması gerekir.
3. Dönüşler doğru birleşiyor mu? return satırını incele. Alt çağrıdan gelen değer, mevcut girdinin katkısıyla doğru biçimde birleşiyor mu kontrol et.

Bu üçlü yöntemi farklı algoritma sorularında uygulamak ve çağrı zincirlerini koddan bağımsız değerlendirmek için Algoritmik Düşünme Testi ile pratik yapabilirsin.

Özyinelemeli ve yinelemeli yaklaşım nasıl karşılaştırılır?

Özyinelemeli ve yinelemeli yaklaşım aynı faktöriyel problemini çözebilir, ancak ilerleme durumunu farklı biçimde tutar. Özyinelemeli çözüm, faktöriyel tanımını doğrudan ifade eder: mevcut sayı, kendisinden küçük problemin sonucu ile birleştirilir. Yinelemeli çözümde ise bu ilerleme bir döngü ve biriktirici değişken aracılığıyla açıkça yönetilir.

def faktoriyel_yinelemeli(n):
    sonuc = 1
    for sayi in range(2, n + 1):
        sonuc *= sayi
    return sonuc

print(faktoriyel_yinelemeli(4))

Beklenen çıktı: 24

Bu örnekte sonuc değişkeni, döngünün her turunda o ana kadar hesaplanan değeri taşır. Özyinelemeli çözümde ise her etkin çağrı kendi parametrelerini ve bekleyen işlemini bir çağrı çerçevesi olarak call stack üzerinde tutar. Bu nedenle çağrı derinliği, özyinelemeli bir çözüm değerlendirilirken ayrıca incelenmesi gereken bir unsurdur.

Problemin matematiksel tanımı kendisini daha küçük bir problem üzerinden açıklıyorsa veya iç içe yapılarla çalışılıyorsa özyinelemeli anlatım daha doğal olabilir. Tekrarlanan işlemlerde durumun sayaç ve biriktirici değişkenlerle açıkça taşınması ise yinelemeli yaklaşımı anlaşılır kılabilir. Seçim, problemin yapısı, kodun okunabilirliği, durum yönetimi ve çağrı derinliğinin kontrol edilebilirliği birlikte değerlendirilerek yapılmalıdır.

Özyinelemeyi değerlendirirken çağrı zincirini üçlü kayıtla incelemek, yaklaşım seçerken de problemin yapısını ve taşınan durumu birlikte düşünmek sağlam bir başlangıç sağlar.