Özyineleme

Bir fonksiyon, gövdesinde başka bir fonksiyonu çağırabiliyorsa, kendisini de çağırabilir. Bu, tanım gereği izin verilen bir durumdur ve özyineleme (recursion) olarak adlandırılır.

İlk bakışta döngüsel görünen bu fikir, çağrı yığıtı bilindiğinde açıklığa kavuşur: her çağrı kendi çerçevesine sahiptir, dolayısıyla aynı fonksiyonun birden çok çağrısı aynı anda, birbirinden bağımsız değişkenlerle var olabilir.

İki Zorunlu Parça

Her özyinelemeli tanım iki parçadan oluşur:

Taban durumu: Özyineleme yapılmadan doğrudan yanıtlanan en küçük durum.

İndirgeme adımı: Problemi, aynı problemin daha küçük bir örneğine dönüştüren adım.

İkisinden biri eksikse çözüm çalışmaz. Taban durumu yoksa çağrılar sonsuza kadar sürer; indirgeme problemi küçültmüyorsa taban duruma hiç ulaşılmaz.

def faktoriyel(n: int) -> int:
    """n! değerini hesaplar. n negatif olmamalıdır."""
    if n < 0:
        raise ValueError("negatif değer")
    if n <= 1:              # taban durumu
        return 1
    return n * faktoriyel(n - 1)     # indirgeme: n, n-1'e iner

print(faktoriyel(5))        # 120
print(faktoriyel(0))        # 1

Taban durumunun n <= 1 biçiminde yazılması, hem $0$ hem $1$ için doğru yanıtı verir ve negatif olmayan her girdinin taban duruma ulaşmasını güvenceye alır.

Yığıtta Açılım

faktoriyel(4) çağrısının yürütülmesi, çerçevelerin üst üste birikmesi ve sonra ters sırada çözülmesi biçiminde ilerler:

faktoriyel(4)
= 4 * faktoriyel(3)
= 4 * (3 * faktoriyel(2))
= 4 * (3 * (2 * faktoriyel(1)))
= 4 * (3 * (2 * 1))          ← taban duruma ulaşıldı
= 4 * (3 * 2)
= 4 * 6
= 24

Yukarı doğru giden satırlar çağrıların açılmasını, aşağı doğru inen satırlar dönüşlerin toplanmasını gösterir. En derin noktada dört çerçeve aynı anda yığıttadır; her birinin kendi n değeri vardır.

Bu, önceki kursta kurulan çerçeve modelinin en açık örneğidir: n değişkeni tek bir bellek gözü değildir, her çağrının çerçevesinde ayrı ayrı bulunur.

Sonsuz Özyineleme

Taban durumu unutulduğunda veya indirgeme problemi küçültmediğinde, çağrılar birikir ve yığıt tükenir.

def hatali(n: int) -> int:
    return n * hatali(n - 1)     # taban durumu yok

# hatali(5)  -> özyineleme sınırı aşıldı hatası

Önceki kursun bellek düzeni dersinde bu davranış tanımlanmıştı: her çağrı bir çerçeve ekler, hiçbiri dönmez ve yığıt için ayrılan alan tükenir. Çalışma zamanı koruması olan dillerde denetimli bir hata alınır; olmayanlarda süreç sonlandırılır.

Hata iletisi genellikle aynı fonksiyon adını yüzlerce kez içerir — bu, sonsuz özyinelemenin ayırt edici imzasıdır.

Doğal Özyinelemeli Problemler

Özyineleme, problemin kendisi özyinelemeli tanımlıysa doğal çözümdür. Ölçüm listesinin toplamı böyle tanımlanabilir: boş listenin toplamı sıfırdır; boş olmayan bir listenin toplamı, ilk eleman artı geri kalanın toplamıdır.

def toplam(olcumler: list[int]) -> int:
    if not olcumler:                        # taban durumu: boş liste
        return 0
    return olcumler[0] + toplam(olcumler[1:])   # indirgeme: bir eleman eksil

print(toplam([12, 18, 7]))     # 37
print(toplam([]))              # 0

Bu çözüm, tanımın birebir çevirisidir; okunması kolaydır. Buna karşılık her çağrıda listenin geri kalanını kopyalar ve eleman sayısı kadar çerçeve açar — aynı işi yapan bir döngü, tek çerçeveyle ve kopyasız çalışır.

Özyinelemenin gerçekten üstün olduğu yerler, verinin kendisinin dallandığı problemlerdir: ağaç yapılarının gezilmesi, dizinlerin alt dizinleriyle birlikte taranması, böl ve yönet algoritmaları. Bu yapılar Veri Yapıları ve Algoritmalar kurslarının konusudur; oradaki çözümlerin çoğu özyinelemeli yazılır.

Maliyet ve Tekrar Eden Hesap

Özyinelemenin iki maliyeti vardır: çerçeve başına bellek ve çağrı başına ek işlem. Üçüncü ve daha sinsi bir maliyet, aynı hesabın tekrarlanmasıdır.

Fibonacci dizisinin doğrudan özyinelemeli tanımı bunun kanonik örneğidir:

def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))          # 55

fib(5) hesaplanırken fib(3) iki kez, fib(2) üç kez hesaplanır. Girdi büyüdükçe tekrar sayısı üstel olarak artar; fib(30) için milyonun üzerinde çağrı yapılır.

Çözüm, hesaplanan değerleri saklamaktır:

def fib_bellekli(n: int, bellek: dict[int, int] | None = None) -> int:
    if bellek is None:
        bellek = {}
    if n < 2:
        return n
    if n in bellek:                 # daha önce hesaplandıysa yeniden hesaplama
        return bellek[n]
    bellek[n] = fib_bellekli(n - 1, bellek) + fib_bellekli(n - 2, bellek)
    return bellek[n]

print(fib_bellekli(30))             # 832040

Not almanın önkoşulu, fonksiyonun aynı girdi için her zaman aynı sonucu vermesidir; girdisi dışında bir duruma bağlı bir fonksiyonun sonucu saklanamaz. Bu tekniğe not alma (memoization) denir ve dinamik programlamanın temelidir; ileri algoritmalar kursunda genel biçimiyle ele alınır. Buradaki ders şudur: özyineleme çözümün yapısını verir, ancak verimliliği kendiliğinden getirmez.

Karşılıklı Özyineleme

Özyineleme, fonksiyonun doğrudan kendini çağırmasıyla sınırlı değildir. İki fonksiyon birbirini çağırarak da özyinelemeli bir yapı kurabilir; buna karşılıklı özyineleme denir.

def cift_mi(n: int) -> bool:
    if n == 0:
        return True
    return tek_mi(n - 1)

def tek_mi(n: int) -> bool:
    if n == 0:
        return False
    return cift_mi(n - 1)

print(cift_mi(4), tek_mi(4))     # True False

Bu örnek, kavramı göstermek içindir; aynı soru kalan işleciyle tek adımda yanıtlanır. Karşılıklı özyinelemenin gerçek kullanım alanı, birbirine bağlı tanımların doğal olarak karşılıklı olduğu yapılardır — dilbilgisi kurallarını işleyen ayrıştırıcılar bunun tipik örneğidir: bir ifade tanımı terim tanımına, terim tanımı yeniden ifade tanımına başvurur.

Taban durumu kuralı burada da geçerlidir, ancak sınanması güçleşir: sonlanma güvencesi tek bir fonksiyonda değil, çağrı zincirinin tamamında aranır.

Özyineleme mi Döngü mü

Seçim ölçütleri:

Ölçüt	Özyineleme	Döngü
Problem tanımı dallanıyor	Doğal	Elle yığıt yönetimi gerekir
Doğrusal ilerleme var	Çerçeve maliyeti öder	Daha ucuz
Derinlik girdiyle büyüyor	Yığıt sınırı riski	Sınır yok
Okunabilirlik	Tanıma yakın	Adımlara yakın

Genel kural: problem özyinelemeli tanımlanıyorsa özyineleme, tekrar doğrusalsa döngü. Her özyinelemeli çözüm döngüye çevrilebilir; çeviri, elle bir yığıt tutmayı gerektirebilir.

Özet

• Özyineleme, bir fonksiyonun kendini çağırmasıdır; her çağrının kendi çerçevesi olduğu için değişkenler karışmaz.
• Her özyinelemeli tanım taban durumu ve indirgeme adımı içerir; biri eksikse çözüm çalışmaz.
• Çağrılar yığıtta birikir, taban durumda açılım durur ve dönüşler ters sırada toplanır.
• Sonsuz özyineleme yığıtı tüketir; imzası, hata iletisinde tekrar eden fonksiyon adıdır.
• Özyineleme dallanan yapılarda doğaldır; doğrusal tekrarlarda döngü daha ucuzdur.
• Aynı alt problemin tekrar hesaplanması üstel maliyet üretebilir; not alma bu tekrarı ortadan kaldırır.

Sonraki Adım

Doğrusal özyinelemelerde çerçeve maliyeti kaçınılmaz görünüyor. Oysa çağrı, gövdenin son işlemi olduğunda durum değişir: yeni bir çerçeve açmak gerekmez. Sonraki ders bu özel biçimi — kuyruk özyinelemesini — ve döngüye denkliğini ele alacak.