Kuyruk Özyinelemesi

Önceki ders, doğrusal özyinelemelerde her çağrının bir çerçeve maliyeti getirdiğini gösterdi. Bu maliyet her zaman kaçınılmaz değildir. Belirli bir yazım biçiminde, çerçeveyi saklamak için hiçbir neden kalmaz.

Bu dersin konusu o biçim ve onun döngülerle olan tam denkliğidir.

Kuyruk Konumu

Bir çağrı, fonksiyonun yaptığı son işlemse kuyruk konumundadır: çağrı döndüğünde yapılacak başka bir iş kalmaz, dönen değer doğrudan dışarı verilir.

Önceki dersteki faktöriyel bu koşulu sağlamaz:

def faktoriyel(n: int) -> int:
    if n <= 1:
        return 1
    return n * faktoriyel(n - 1)      # çağrı döndükten SONRA çarpma var

Son satırda özyinelemeli çağrı sonuncu işlem değildir; sonucu n ile çarpılacaktır. Bu nedenle çağıran çerçeve, alt çağrı dönene kadar bekletilmek zorundadır — n değerini ve nereye döneceğini tutar.

Aynı hesabın kuyruk biçimi, henüz yapılmamış işi bir birikeç parametresine taşır:

def faktoriyel_kuyruk(n: int, birikec: int = 1) -> int:
    """n! değerini kuyruk özyinelemeli biçimde hesaplar."""
    if n <= 1:
        return birikec                       # taban durumu: birikeci döndür
    return faktoriyel_kuyruk(n - 1, n * birikec)   # son işlem: çağrının kendisi

print(faktoriyel_kuyruk(5))     # 120
print(faktoriyel(5))            # 120  — aynı sonuç

Çarpma artık çağrıdan önce, argüman hazırlanırken yapılır. Çağrı döndüğünde yapılacak iş kalmadığı için, çağıran çerçevenin korunmasına gerek yoktur.

Çerçeve Neden Gerekmez

Çerçeve iki şey için saklanır: dönüş adresi ve yerel değerler. Kuyruk konumunda alt çağrının dönüş değeri doğrudan dışarı verileceğinden, çağıranın dönüş adresi ile alt çağrının dönüş adresi aynıdır. Yerel değerlere de artık gerek yoktur; hepsi argümanlara aktarılmıştır.

Dolayısıyla yeni bir çerçeve açmak yerine, var olan çerçevenin yeniden kullanılması mümkündür. Bu dönüşüme kuyruk çağrısı eniyilemesi denir. Uygulandığında, özyineleme derinliği ne olursa olsun yığıt büyümez.

Dil Desteği Evrensel Değildir

Bu eniyilemenin yapılıp yapılmadığı dile ve gerçekleştirime bağlıdır ve dilin tanımının parçasıdır — bir hız ayrıntısı değil. Bazı diller eniyilemeyi garanti eder; o dillerde derin kuyruk özyinelemesi güvenle yazılabilir. Bazıları hiç uygulamaz.

Python uygulamayan diller arasındadır. Kuyruk biçiminde yazılmış bir fonksiyon bile, derinlik arttığında özyineleme sınırına çarpar:

# faktoriyel_kuyruk(5000)  -> özyineleme sınırı aşıldı hatası

Bunun gerekçesi tasarım tercihidir: çerçeveler korunduğunda hata izleme dökümü eksiksiz kalır ve hata ayıklama kolaylaşır. Ödünleşim, derin özyinelemenin kullanılamamasıdır.

Sonuç şudur: kuyruk biçiminde yazmak, tek başına derinlik güvencesi vermez. Dilin bu eniyilemeyi yapıp yapmadığı bilinmelidir.

Özyineleme sınırının yükseltilebildiği çalışma zamanlarında bu, çözüm gibi görünür ama değildir: sınır, gerçek yığıt alanının tükenmesinden önce uyarı vermek için konmuştur. Yükseltilen sınır, denetimli hatayı denetimsiz bir çökmeye çevirebilir. Doğru çözüm, derinliği veriyle birlikte büyüyen bir çözümü özyinelemeden çıkarmaktır.

Döngüye Denklik

Kuyruk özyinelemesi ile döngü arasındaki ilişki mekaniktir. Birikeç parametreleri döngü değişkenlerine, indirgeme adımı güncellemelere, taban durumu ise döngü koşuluna karşılık gelir.

def faktoriyel_dongu(n: int) -> int:
    birikec = 1
    while n > 1:                 # taban durumunun olumsuzu
        birikec = n * birikec    # özyinelemeli çağrının argümanları
        n = n - 1
    return birikec

print(faktoriyel_dongu(5))       # 120

Üç sürüm de aynı değeri üretir. Farkları yalnızca yazımda ve yığıt davranışındadır: döngü sürümü tek çerçeve kullanır ve derinlik sınırı tanımaz.

Karşılıklar tek tek eşlenebilir: birikeç parametresi döngü değişkenine, taban durumunun olumsuzu döngü koşuluna, özyinelemeli çağrının argümanları ise gövdedeki güncellemelere karşılık gelir. Bu eşleme, döngü değişmezi kavramının özyinelemedeki karşılığını da verir — birikecin her çağrıda taşıdığı anlam, döngü değişmezinin tam olarak kendisidir.

Bu denklik, kuyruk çağrısı eniyilemesinin ne yaptığını da açıklar: dönüşümü derleyici otomatik uygular, elde edilen kod döngü sürümünün kodudur.

Kuyruk Olmayan Özyinelemeyi Döngüye Çevirmek

Her özyinelemeli çözüm döngüye çevrilebilir; ancak çağrı kuyruk konumunda değilse çeviri mekanik olmaz. Çağrıdan sonra yapılacak iş bir yerde saklanmak zorundadır ve çerçeve kaldırıldığında bu görev programa geçer: yığıt elle tutulur.

Ağaç benzeri bir yapıyı gezmek bunun tipik örneğidir. Aşağıdaki çözüm, iç içe listeleri özyineleme kullanmadan düzleştirir:

def duzlestir(veri: list) -> list[int]:
    """İç içe listeleri tek düzeye indirir; özyineleme kullanmaz."""
    sonuc = []
    yigit = [veri]                       # işlenecek parçalar
    while yigit:
        parca = yigit.pop()
        if isinstance(parca, list):
            yigit.extend(reversed(parca))   # sırayı korumak için ters ekle
        else:
            sonuc.append(parca)
    return sonuc

print(duzlestir([1, [2, [3, 4]], 5]))    # [1, 2, 3, 4, 5]

Buradaki yigit listesi, özyinelemeli sürümde çağrı yığıtının yaptığı işi yapar: henüz işlenmemiş parçaları tutar. Kod uzar ve okunabilirlik düşer; karşılığında derinlik sınırı ortadan kalkar ve bellek kullanımı denetlenebilir hâle gelir.

Seçim ölçütü nettir: derinlik girdiyle sınırsız büyüyorsa ve dil kuyruk çağrısı eniyilemesi yapmıyorsa, yığıt elle tutulur.

Ne Zaman Hangi Biçim

Üç yazım biçiminin seçimi bağlama bağlıdır.

Doğrudan özyineleme, problem tanımına en yakın olanıdır ve okunması en kolayıdır. Derinlik küçük ve sınırlıysa tercih edilir.

Kuyruk biçimi, eniyilemeyi garanti eden dillerde derin tekrarlar için doğru seçimdir. Birikeç parametresi eklendiği için okunabilirlik bir miktar düşer; bu nedenle birikeçli sürüm genellikle bir yardımcı fonksiyona alınır ve dış arayüz sade tutulur:

def faktoriyel_temiz(n: int) -> int:
    """Dış arayüz sade; birikeç ayrıntısı gizlenir."""
    def yardimci(k: int, birikec: int) -> int:
        if k <= 1:
            return birikec
        return yardimci(k - 1, k * birikec)
    return yardimci(n, 1)

print(faktoriyel_temiz(5))       # 120

Bu yazım, kapsam dersindeki iç fonksiyon fikrinin doğrudan uygulamasıdır: yardımcı fonksiyon dışarıdan görünmez, yalnızca kendi bağlamında anlamlıdır.

Döngü, eniyileme garantisi olmayan dillerde ve derinliğin girdiyle büyüdüğü durumlarda güvenli seçimdir.

Bu üçlü seçim, dillerin tasarım tercihlerini de açıklar. Değiştirilemezliği önceleyen diller, döngü değişkenini yeniden bağlamak yerine özyinelemeyi asıl tekrar aracı sayar; bu dillerde kuyruk çağrısı eniyilemesi bir kolaylık değil, zorunluluktur. Buna karşılık döngüyü asıl araç sayan diller, eniyilemeyi yapmasalar da bir eksiklik doğurmaz — çünkü aynı işi zaten döngüyle yazmak beklenir. Bir dilin hangi yolu seçtiği, o dilde yazılmış kodun nasıl göründüğünü belirler; bu ilişki sonraki konunun ana fikridir.

Özet

• Bir çağrı, fonksiyonun son işlemiyse kuyruk konumundadır; dönüşten sonra yapılacak iş kalmaz.
• Doğrudan özyineleme, henüz yapılmamış işi birikeç parametresine taşıyarak kuyruk biçimine çevrilir.
• Kuyruk konumunda çağıran çerçevesi yeniden kullanılabilir; bu dönüşüme kuyruk çağrısı eniyilemesi denir.
• Eniyilemenin uygulanması dile bağlıdır ve evrensel değildir; kuyruk biçiminde yazmak tek başına derinlik güvencesi vermez.
• Kuyruk özyinelemesi ile döngü arasındaki dönüşüm mekaniktir: birikeçler döngü değişkeni, taban durumu döngü koşulu olur.
• Birikeç ayrıntısı, iç yardımcı fonksiyona alınarak dış arayüzden gizlenir.

Sonraki Adım

Bu konu, fonksiyonu bir soyutlama aracı olarak kurdu: iş adlandırılır, girdi ve çıktı sözleşmeye bağlanır, kapsam yalıtılır. Fonksiyon tek soyutlama aracı değildir. Sonraki konu, programları düzenlemenin üç ayrı yaklaşımını — yapısal, nesneye dayalı ve fonksiyonel — karşılaştıracak ve aynı problemi her biriyle çözecek.