Özyineleme (recursion)

Kendine benzeyen problemler

Anadolu Market'in ürün kategorilerini düşün: "Elektronik" altında "Telefon", onun altında "Akıllı telefon" ve "Aksesuar", aksesuarın altında "Kılıf" ve "Şarj aleti". Kaç katman olduğu belli değil; yarın bir katman daha eklenebilir. Kategori ağacındaki toplam ürün sayısını nasıl hesaplarsın? İç içe kaç döngü yazacağını bilemezsin.

Ama şu cümle her katman için doğrudur: "Bir kategorinin ürün sayısı, kendi ürünleri artı her alt kategorinin ürün sayısıdır." Cümlenin içinde aynı soru, daha küçük bir parça için tekrar soruluyor. İşte özyineleme (recursion) budur: bir fonksiyonun, problemi daha küçük bir parçası için kendini çağırması. Klasör ağaçları, organizasyon şemaları, iç içe yorum dizileri, JSON belgeleri, matematikteki faktöriyel ve fibonacci hep bu yapıdadır.

İki zorunlu parça

Her özyinelemeli fonksiyonun iki parçası vardır:

• Temel durum (base case): cevabı doğrudan bilinen, kendini çağırmayan en küçük durum. Olmazsa fonksiyon sonsuza dek kendini çağırır.
• Özyinelemeli adım (recursive step): problemi küçültüp kendini çağıran ve gelen cevabı kullanarak sonucu kuran kısım. Her çağrı temel duruma biraz daha yaklaşmalı.

def geri_say(n):
    if n == 0:                 # temel durum
        print("Kampanya başladı!")
        return
    print(n)
    geri_say(n - 1)            # özyinelemeli adım: n küçülüyor

geri_say(3)

def faktoriyel(n):
    if n <= 1:                 # temel durum: 0! = 1! = 1
        return 1
    return n * faktoriyel(n - 1)

print(faktoriyel(5))
print(faktoriyel(0))

Faktöriyelin matematiksel tanımı zaten özyinelemelidir: n! = n × (n-1)! ve 0! = 1. Kod bu tanımın neredeyse birebir kopyası. Özyinelemeyi tasarlarken kendine iki soru sor: "En küçük, cevabını doğrudan bildiğim durum ne?" ve "Bir küçüğünün cevabını bilseydim, bunun cevabını nasıl kurardım?" İkinci soruda küçüğün cevabının doğru geleceğine güvenirsin; buna "özyinelemeli inanç sıçraması" (recursive leap of faith) denir.

Çağrı yığınını görmek

Bir fonksiyon çağrıldığında Python onun yerel değişkenlerini bir çerçeve (frame) içinde tutar ve çerçeveyi çağrı yığınının (call stack) tepesine koyar. Fonksiyon dönünce çerçeve yığından kalkar. Özyinelemede aynı fonksiyonun birçok çerçevesi aynı anda yığında bekler; her birinin kendi n'i vardır. Bunu görmenin en iyi yolu, derinliği bir parametreyle taşıyıp girintili yazdırmaktır.

def faktoriyel_iz(n, derinlik=0):
    girinti = "    " * derinlik
    print(f"{girinti}faktoriyel({n}) çağrıldı")
    if n <= 1:
        print(f"{girinti}temel durum → 1")
        return 1
    alt = faktoriyel_iz(n - 1, derinlik + 1)
    sonuc = n * alt
    print(f"{girinti}faktoriyel({n}) = {n} × {alt} = {sonuc}")
    return sonuc

faktoriyel_iz(4)

Çıktıda iki aşama görürsün: iniş sırasında çağrılar açılır ve hiçbiri henüz bitmemiştir (çarpma bekliyor); temel duruma varınca çıkış başlar ve her çerçeve, alttan gelen cevapla kendi çarpmasını yapıp yukarıya döner. Özyinelemeli adımdan sonra yazılan kod çıkış sırasında, yani ters sırayla çalışır.

Liste üzerinde özyineleme

Listeler de doğal olarak özyinelemelidir: bir liste, "ilk eleman" ile "geri kalan liste"den oluşur. Boş liste temel durumdur.

def toplam(liste):
    if not liste:                          # boş liste
        return 0
    return liste[0] + toplam(liste[1:])

def ters(metin):
    if len(metin) <= 1:
        return metin
    return ters(metin[1:]) + metin[0]

print(toplam([120, 80, 45.5]))
print(ters("Anadolu"))

Bu örnekler kavramı öğretmek içindir; gerçek kodda sum ve [::-1] kullanırsın. Ayrıca liste[1:] her çağrıda yeni bir kopya oluşturur; uzun listelerde hem yavaş hem de yığın derinliği sınırına takılır. Özyinelemenin asıl gücü, düz listelerde değil, derinliği bilinmeyen yapılarda ortaya çıkar.

İç içe liste: derinliği bilinmeyen yapı

Bir depo sayım listesi, raflar içinde kutular, kutular içinde paketler olarak iç içe gelmiş olsun. Kaç katman olduğunu bilmeden tüm adetleri toplamak döngüyle zordur; özyinelemeyle doğaldır: her eleman ya bir sayıdır (temel durum) ya da yine bir listedir (özyinelemeli adım).

depo = [12, [3, 4, [10, 2]], [], [[[7]]], 1]

def ic_ice_toplam(veri):
    toplam = 0
    for x in veri:
        if isinstance(x, list):
            toplam += ic_ice_toplam(x)     # alt liste: aynı soruyu sor
        else:
            toplam += x                    # sayı: doğrudan ekle
    return toplam

def derinlik(veri):
    if not isinstance(veri, list):
        return 0
    en = 0
    for x in veri:
        en = max(en, derinlik(x))
    return 1 + en

print(ic_ice_toplam(depo))
print(derinlik(depo))

Burada döngü ve özyineleme birlikte çalışıyor: döngü bir katmandaki kardeşleri gezer, özyineleme bir katman aşağı iner. Ağaç gezen fonksiyonların çoğu bu şekildedir. Temel durum ayrı bir if olarak değil, "liste değilse doğrudan ekle" dalı olarak gizlenmiştir.

Klasör ağacı gezmek

Dosya sistemi en tanıdık ağaçtır. Gerçek diske dokunmadan iç içe sözlükle simüle edelim: değer bir sayıysa dosya (boyutu KB), sözlükse klasördür.

disk = {
    "raporlar": {
        "2025": {"ocak.csv": 120, "subat.csv": 135},
        "ozet.pdf": 900,
    },
    "gorseller": {"logo.png": 48, "kampanya": {"banner.png": 310}},
    "notlar.txt": 4,
}

def toplam_boyut(klasor):
    toplam = 0
    for ad, icerik in klasor.items():
        if isinstance(icerik, dict):
            toplam += toplam_boyut(icerik)
        else:
            toplam += icerik
    return toplam

def agac_yazdir(klasor, derinlik=0):
    for ad, icerik in klasor.items():
        girinti = "  " * derinlik
        if isinstance(icerik, dict):
            print(f"{girinti}{ad}/  ({toplam_boyut(icerik)} KB)")
            agac_yazdir(icerik, derinlik + 1)
        else:
            print(f"{girinti}{ad}  {icerik} KB")

agac_yazdir(disk)
print("Toplam:", toplam_boyut(disk), "KB")

Gerçek diskte aynı mantığı pathlib.Path.iterdir() ve is_dir() ile kurarsın; Python'un os.walk fonksiyonu da içeride tam olarak bu gezintiyi yapar.

Fibonacci ve memoization

Fibonacci dizisinde her sayı önceki ikisinin toplamıdır: 0, 1, 1, 2, 3, 5, 8, ... Tanımı özyinelemelidir ve koda doğrudan çevrilir. Ama bir sorun var: her çağrı iki çağrı daha yapar ve aynı değerler tekrar tekrar hesaplanır.

cagri = 0

def fib(n):
    global cagri
    cagri += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

for n in [10, 20, 25]:
    cagri = 0
    print(f"fib({n}) = {fib(n)}, çağrı sayısı: {cagri}")

fib(25) için iki yüz binden fazla çağrı yapılıyor; fib(40) yüz milyonları bulur. Çare: bir kez hesapladığın sonucu bir sözlükte saklayıp tekrar istendiğinde oradan vermek. Bu tekniğe memoization (ezberleme) denir.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print(fib_memo(80))

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cache(n):
    if n < 2:
        return n
    return fib_cache(n - 1) + fib_cache(n - 2)

print(fib_cache(80))
print(fib_cache.cache_info())

memo=None ile başlayıp içeride sözlük oluşturmamızın sebebi, Fonksiyonlar dersindeki değişebilir varsayılan tuzağıdır. @lru_cache ise aynı işi otomatik yapan hazır bir araçtır; başındaki @ işaretiyle yazılan yapıya dekoratör (decorator) denir ve Orta seviyede ayrıntılı göreceksin. Ezberleme yalnızca aynı argümanla aynı sonucu veren (saf) fonksiyonlarda güvenlidir.

İkili arama: özyinelemeli

Sıralı bir listede arama yaparken her adımda ortadaki elemana bakıp aramayı yarıya indirebilirsin: aranan değer ortadakinden küçükse sol yarıda, büyükse sağ yarıda ara. "Yarıda ara" aynı problemin küçüğüdür; temel durum, aralığın boşalmasıdır.

def ikili_ara(liste, hedef, bas=0, son=None):
    if son is None:
        son = len(liste) - 1
    if bas > son:                       # aralık boş: yok
        return -1
    orta = (bas + son) // 2
    print(f"  aralık [{bas}, {son}], orta={orta} ({liste[orta]})")
    if liste[orta] == hedef:
        return orta
    if hedef < liste[orta]:
        return ikili_ara(liste, hedef, bas, orta - 1)
    return ikili_ara(liste, hedef, orta + 1, son)

musteri_nolari = [101, 115, 220, 318, 402, 517, 640, 777, 812, 905]
print("Sonuç:", ikili_ara(musteri_nolari, 640))
print("Sonuç:", ikili_ara(musteri_nolari, 300))

On elemanlı listede en fazla dört adım; bir milyon elemanda yaklaşık yirmi adım. Doğrusal arama bir milyon adım sürebilirdi. Her çağrıda listeyi dilimlemek yerine bas ve son indekslerini taşıdığımıza dikkat et; böylece kopya oluşturmayız.

RecursionError ve yığın sınırı

Yığın sonsuz değildir. Python, çok derin özyinelemeyi bir koruma sınırıyla durdurur ve RecursionError fırlatır. Sınır varsayılan olarak yaklaşık 1000 çerçevedir.

import sys
print("Sınır:", sys.getrecursionlimit())

def sonsuz(n):
    return sonsuz(n + 1)               # temel durum yok!

try:
    sonsuz(0)
except RecursionError as e:
    print("Hata:", e)

def toplam(liste):
    return 0 if not liste else liste[0] + toplam(liste[1:])

try:
    print(toplam(list(range(5000))))
except RecursionError:
    print("5000 elemanlı listede özyinelemeli toplam sınırı aştı")

Döngü mü, özyineleme mi?

disk = {"a": {"b": {"c.txt": 5}, "d.txt": 7}, "e.txt": 1}

def toplam_boyut_yigin(kok):
    toplam = 0
    yigin = [kok]
    while yigin:
        klasor = yigin.pop()
        for icerik in klasor.values():
            if isinstance(icerik, dict):
                yigin.append(icerik)       # sonra gezilecek
            else:
                toplam += icerik
    return toplam

print(toplam_boyut_yigin(disk))