Özyineleme: kendini çağıran fonksiyonlar

Bir fonksiyonun bir problemi, kendisini daha küçük bir hâli için çağırarak nasıl çözdüğü: temel durum ve özyinelemeli adım, çağrı yığını ve `RecursionError`, faktöriyel, Fibonacci, rakamlar toplamı, özyinelemeli ikili arama, iç içe listeler ve klasör ağaçları; ayrıca döngünün ya da `lru_cache` kullanmanın daha iyi olduğu durumlar.

  • Orta
  • 22 dk
  • 12 soru
  • Ders 11 / 66

Bu derste öğreneceklerin

  • Doğru bir temel durumu ve ona doğru ilerleyen özyinelemeli adımı olan bir fonksiyon yazmak
  • Çağrı yığınının nasıl büyüyüp küçüldüğünü ve RecursionError hatasının neden oluştuğunu açıklamak
  • Klasik problemleri özyinelemeyle çözmek: faktöriyel, Fibonacci, rakamlar toplamı, ikili arama
  • İç içe verileri (listeler, klasörler) işlemek ve özyineleme, döngü ve lru_cache arasında seçim yapmak

Bir klasörde dosyalar ve başka klasörler vardır, o klasörlerde de yine dosyalar ve klasörler. İç içeliğin ne kadar derin olduğunu bilmeden bütün dosyaları nasıl sayarsın? for döngüsü neyin üzerinden geçeceğini önceden bilmelidir. Fakat bu problemin güzel bir özelliği var: bir alt klasördeki dosyaları saymak aynı problemdir, yalnızca daha küçüktür. Bir problemi, onun küçük bir parçası için kendini çağırarak çözen fonksiyona özyinelemeli (recursive) fonksiyon denir. «Fonksiyonlar» dersinde fonksiyon tanımlamayı ve çağırmayı öğrendin; şimdi fonksiyon kendi kendini çağıracak.

Özyineleme (recursion)Tanım

Bir fonksiyonun kendisini daha küçük ya da daha basit bir girdiyle çağırdığı çözüm yöntemi. Her özyinelemeli fonksiyonun iki parçası vardır: yeni bir çağrı yapmadan cevabı hemen veren temel durum ve problemi küçültüp fonksiyonu yeniden çağıran özyinelemeli adım.

Temel durum ve özyinelemeli adım

En basit örnek geri sayımdır. countdown(3) 3 yazar ve işin geri kalanını, yani 2’den geri saymayı, countdown(2) çağrısına bırakır. n 0’a ulaşınca fonksiyon Start! yazar ve durur: bu, temel durumdur. Faktöriyel de aynı şekilde kurulur: 5!’i bulmak için 4! gerekir, 4! için 3! ve bu böyle 1! = 1’e kadar gider.

n! = n · (n − 1)!0! = 1! = 1

Burada

n
bir doğal sayı
n!
1 · 2 · … · n çarpımı

Kural aynı işlemi daha küçük bir sayı için tekrarlar (özyinelemeli adım) ve hesaplamadan bildiğimiz bir değer verir (temel durum).

Python
def countdown(n):
    if n == 0:               # base case
        print('Start!')
        return
    print(n)
    countdown(n - 1)         # recursive step


def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)


countdown(3)
print(factorial(5), factorial(10))
Beklenen çıktı
3
2
1
Start!
120 3628800
countdown hiçbir şey döndürmez, yalnızca yazdırır; factorial ise sonucunu return ile kendisini çağırana geri verir.

Örnek: factorial(4) adım adım

Problem

Kodu çalıştırmadan factorial(4) değerini adım adım hesapla ve kaç çağrı yapıldığını söyle.

Çözümü gösterÇözümü gizle

Çözüm

factorial(4) = 4 · factorial(3)
factorial(3) = 3 · factorial(2)
factorial(2) = 2 · factorial(1)
factorial(1) = 1 — temel durum, yeni çağrı yok.
Şimdi sonuçlar geri döner: 2 · 1 = 2, 3 · 2 = 6, 4 · 6 = 24.
Toplam 4 çağrı yapılır: n = 4, 3, 2, 1 için birer tane.

Okumaya devam etmek için ücretsiz kaydol

Dersin geri kalan bölümleri, test ve notlar Educora hesabıyla açılır. Kayıt bir dakika sürer; ilerlemen tüm cihazlarında saklanır.

Çağrı yığını ve RecursionError

Bir fonksiyon aynı anda birkaç kez nasıl çalışabilir? Her çağrı kendi çerçevesini (frame) alır: kendi parametreleri ve yerel değişkenleri olan küçük bir bellek alanı. Çerçeveler çağrı yığınında tutulur: yeni çağrı en üste konur, return ile biten çağrının çerçevesi kaldırılır ve sonuç alttaki çerçeveye iletilir. factorial(1) çalışırken factorial(4), factorial(3) ve factorial(2) yığında bekler; her birinin kendi n değeri vardır.

Çağrı yığını (call stack)Tanım

Başlamış ama henüz bitmemiş fonksiyon çağrılarının «son giren ilk çıkar» kuralıyla dizildiği liste. En üstteki çerçeve şu anda çalışandır, diğerleri onun sonucunu bekler.

↑ yeni çağrı üste konurdönüşfactorial(1)temel durum: 1 döndürürfactorial(2)bekliyor: 2 · factorial(1)factorial(3)bekliyor: 3 · factorial(2)print(factorial(3))program sonucu bekliyor126
Çağrılar yığını yukarı doğru büyütür, her return en üstteki çerçeveyi kaldırır.
Python
def factorial(n, depth=0):
    pad = '    ' * depth
    print(f'{pad}factorial({n}) called')
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f'{pad}factorial({n}) returns {result}')
    return result


print('answer:', factorial(4))
Beklenen çıktı
factorial(4) called
    factorial(3) called
        factorial(2) called
            factorial(1) called
            factorial(1) returns 1
        factorial(2) returns 2
    factorial(3) returns 6
factorial(4) returns 24
answer: 24
Girinti yığının derinliğini gösterir. Çağrılar temel duruma kadar iner, sonuçlar ise ters sırayla geri döner.

Yığın sonsuz değildir. CPython varsayılan olarak yaklaşık 1000 iç içe çağrıya izin verir (sys.getrecursionlimit() sınırı gösterir). Temel durum yoksa ya da ona hiç ulaşılmıyorsa çağrılar bitmez, sınır aşılır ve Python programı RecursionError: maximum recursion depth exceeded hatasıyla durdurur. Aşağıda broken fonksiyonunun hiç temel durumu yok; also_broken fonksiyonunun var, ancak tek bir n için n − 2 adımı 0’ın üzerinden atlar:

Python
def broken(n):
    return n * broken(n - 1)          # no base case


def also_broken(n):
    if n == 0:
        return 0
    return n + also_broken(n - 2)     # an odd n jumps over 0


for func, arg in ((broken, 5), (also_broken, 6), (also_broken, 7)):
    try:
        print(func.__name__, arg, '->', func(arg))
    except RecursionError:
        print(func.__name__, arg, '-> RecursionError')
Beklenen çıktı
broken 5 -> RecursionError
also_broken 6 -> 12
also_broken 7 -> RecursionError
also_broken(6) = 6 + 4 + 2 + 0 = 12. 7 ile dizi 7, 5, 3, 1, −1, … olur ve 0’a hiç rastlamaz. Daha güvenli bir temel durum if n <= 0 olurdu.

`return` unutulmuş

def digit_sum(n):
    if n < 10:
        return n
    n % 10 + digit_sum(n // 10)

doğru

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)
return olmadan digit_sum(25) None döndürür, 2026 için ise program çöker bile: bir üst seviyede Python 2 + None hesaplamak zorunda kalır ve TypeError: unsupported operand type(s) for +: 'int' and 'NoneType' hatası verir.

Klasik problemler: rakamlar toplamı, Fibonacci, ikili arama

Matematikteki birçok tanım zaten özyinelemelidir. Bir sayının rakamları toplamı, son rakamı (n % 10) artı bu rakam olmadan kalan sayının (n // 10) rakamları toplamıdır; tek basamaklı bir sayının rakamları toplamı sayının kendisidir. Fibonacci sayıları dizinin önceki iki terimiyle tanımlanır.

S(n) = n % 10 + S(n // 10)S(n) = n, if n < 10

Burada

S(n)
n sayısının rakamları toplamı
n % 10
10’a bölümden kalan, yani son rakam
n // 10
tam bölme, son rakamı atar

S(2026) = 6 + S(202) = 6 + 2 + S(20) = 6 + 2 + 0 + S(2) = 10.

F(n) = F(n − 1) + F(n − 2)F(0) = 0F(1) = 1

Burada

F(n)
n’inci Fibonacci sayısı

Adım iki terim geriye baktığı için iki temel durum gerekir.

Python
def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)


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


print(digit_sum(2026), digit_sum(4096), digit_sum(987654321))
print([fib(n) for n in range(12)])
Beklenen çıktı
10 19 45
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
4096 → 6 + 9 + 0 + 4 = 19; 987654321 → 9 + 8 + … + 1 = 45.

Örnekler: sonucu önceden söyle

Problem

1) digit_sum(507); 2) fib(7); 3) 6 basamaklı bir sayı için digit_sum kaç kez çağrılır?

Çözümü gösterÇözümü gizle

Çözüm

1) 7 + digit_sum(50) = 7 + 0 + digit_sum(5) = 7 + 0 + 5 = 12.
2) F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8, F(7) = 13.
3) Her çağrı tek rakam kalana kadar bir rakam atar: 6 basamaklı sayı için 6 çağrı (k basamak, k çağrı).

Fibonacci fonksiyonu kısadır ama çok yavaştır. Her çağrı iki çağrı daha yapar ve aynı değerler tekrar tekrar hesaplanır: fib(5), fib(3) değerini iki kez, fib(2) değerini üç kez hesaplar. Çağrı sayısı neredeyse Fibonacci sayılarının kendisi kadar hızlı büyür:

calls(n) = 2 · F(n + 1) − 1

Burada

calls(n)
basit fib(n) fonksiyonunun yaptığı çağrı sayısı

n = 20 için F(21) = 10946, yani 2 · 10946 − 1 = 21891 çağrı; aşağıdaki program da tam bu kadar sayar.

Python
from functools import lru_cache

calls = 0


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


for n in (10, 20, 25):
    calls = 0
    value = fib(n)
    print(f'fib({n}) = {value}: {calls} calls')


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


def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib_cached(90), fib_loop(90), fib_cached.cache_info().misses)
Beklenen çıktı
fib(10) = 55: 177 calls
fib(20) = 6765: 21891 calls
fib(25) = 75025: 242785 calls
2880067194370816120 2880067194370816120 91
lru_cache her sonucu hatırlar, bu yüzden fib_cached(90) yalnızca 91 gerçek hesaplama (misses) yapar: 0’dan 90’a kadar her n için bir tane. Döngü sürümü yalnızca son iki sayıyı tutar ve yığına hiç ihtiyaç duymaz. lru_cache’in nasıl çalıştığı «Dekoratörler ve kapanışlar» dersinde anlatılır.

İkili arama, sıralı bir listede bir değeri her adımda aralığı ikiye bölerek bulur; her adım aynı problemi verinin yarısında çözer. Listeyi dilimlemek yerine lo ve hi sınırlarını geçiriyoruz, çünkü her dilim elemanların kopyasını çıkarırdı.

  1. Boş aralık

    lo > hi ise değer yoktur: -1 döndür (temel durum).

  2. Ortadaki eleman

    mid = (lo + hi) // 2; items[mid] == target ise mid döndür (temel durum).

  3. Sağ yarı

    items[mid] < target ise [mid + 1..hi] aralığında ara.

  4. Sol yarı

    Aksi hâlde [lo..mid − 1] aralığında ara.

Python
def binary_search(items, target, lo=0, hi=None):
    if hi is None:
        hi = len(items) - 1
    if lo > hi:                          # base case: nothing left
        return -1
    mid = (lo + hi) // 2
    print(f'  range [{lo}..{hi}], items[{mid}] = {items[mid]}')
    if items[mid] == target:             # base case: found
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, hi)
    return binary_search(items, target, lo, mid - 1)


scores = [12, 25, 31, 47, 58, 63, 77, 84, 90, 96]
print('77 at index', binary_search(scores, 77))
print('50 at index', binary_search(scores, 50))
Beklenen çıktı
  range [0..9], items[4] = 58
  range [5..9], items[7] = 84
  range [5..6], items[5] = 63
  range [6..6], items[6] = 77
77 at index 6
  range [0..9], items[4] = 58
  range [0..3], items[1] = 25
  range [2..3], items[2] = 31
  range [3..3], items[3] = 47
50 at index -1
10 eleman için en fazla 4 adım gerekir: aralık 10 → 5 → 2 → 1 diye küçülür. Bir milyon eleman için yaklaşık 20 adım yeter, çünkü 2²⁰ ≈ 10⁶.

Etkileşimli

Simülasyon yükleniyor…
İkili aramanın aralığı adım adım nasıl ikiye böldüğünü izle.

Özyinelemeli veriler: iç içe listeler ve klasör ağaçları

Özyineleme en doğal hâlini verinin kendisi özyinelemeli olduğunda alır: listelerin içinde listeler, klasörlerin içinde klasörler, yanıtlarına da yanıt yazılan yorumlar. Fonksiyonun yapısı verinin yapısını izler: sıradan bir eleman temel durumdur, iç içe bir eleman için fonksiyon kendini yeniden çağırır.

Python
def total(data):
    result = 0
    for item in data:
        if isinstance(item, list):
            result += total(item)        # a smaller list of the same kind
        else:
            result += item
    return result


def depth(data):
    if not isinstance(data, list):
        return 0
    return 1 + max((depth(x) for x in data), default=0)


expenses = [120, [30, 45, [5, 5]], 60, [[10], 20]]
print(total(expenses), depth(expenses))
print(total([]), depth([]), depth(7))
Beklenen çıktı
295 3
0 1 0
total her derinlikteki bütün sayıları toplar: 120 + 30 + 45 + 5 + 5 + 60 + 10 + 20 = 295. depth köşeli parantez düzeylerini sayar; default=0 boş listeyi karşılar.

Bir klasör ağacı iç içe sözlüklerle tanımlanabilir: anahtar addır, sayı KB cinsinden dosya boyutudur, sözlük ise alt klasördür. Fonksiyon ağacı yazdırır ve boyutunu döndürür; her alt klasörü aynı fonksiyon bir düzey daha derinde işler:

Python
tree = {
    'school': {
        'math': {'algebra.pdf': 320, 'geometry.pdf': 410},
        'photos': {'trip': {'baku.jpg': 2048, 'quba.jpg': 1730}, 'class.png': 960},
        'plan.txt': 12,
    }
}


def show(folder, indent=0):
    size = 0
    for name, content in folder.items():
        if isinstance(content, dict):          # a folder: recurse
            print('    ' * indent + name + '/')
            size += show(content, indent + 1)
        else:                                  # a file: base case
            print('    ' * indent + f'{name} ({content} KB)')
            size += content
    return size


print('Total:', show(tree), 'KB')
Beklenen çıktı
school/
    math/
        algebra.pdf (320 KB)
        geometry.pdf (410 KB)
    photos/
        trip/
            baku.jpg (2048 KB)
            quba.jpg (1730 KB)
        class.png (960 KB)
    plan.txt (12 KB)
Total: 5480 KB

Şimdi gerçek bir disk. pathlib modülünde Path.iterdir() bir klasörün içeriğini listeler, is_dir() ise klasörü dosyadan ayırır. Program önce küçük bir proje klasörü oluşturur (bu da özyinelemelidir), sonra onu dolaşır ve her klasördeki dosya ve bayt sayısını bildirir:

Python
from pathlib import Path


def make(folder, spec):
    for name, content in spec.items():
        path = folder / name
        if isinstance(content, dict):
            path.mkdir()
            make(path, content)
        else:
            path.write_text('x' * content)


def report(folder, indent=0):
    files, size = 0, 0
    for path in sorted(folder.iterdir()):
        if path.is_dir():
            f, s = report(path, indent + 1)
            print('  ' * indent + f'{path.name}/  files={f}, bytes={s}')
            files, size = files + f, size + s
        else:
            files, size = files + 1, size + path.stat().st_size
    return files, size


root = Path('project')
root.mkdir()
make(root, {'docs': {'a.txt': 120, 'b.txt': 80, 'old': {'c.txt': 300}},
            'src': {'main.py': 450}, 'readme.md': 50})
print(report(root))
print(sum(p.stat().st_size for p in root.rglob('*') if p.is_file()))
Beklenen çıktı
  old/  files=1, bytes=300
docs/  files=3, bytes=500
src/  files=1, bytes=450
(5, 1000)
1000
Bir klasörün satırı alt klasörlerinin satırlarından sonra yazdırılır, çünkü toplamlar ancak onlar sayıldıktan sonra bilinir. rglob('*') ağacı senin yerine dolaşır ve aynı 1000 baytı verir: gerçek betiklerde hazır araçlar rglob ve os.walk’tur, ama içeride tam olarak bunu yaparlar.

Özyineleme mi, döngü mü?

Her özyinelemeli fonksiyon bir döngüyle (gerekirse kendi yığın listenle) yeniden yazılabilir, tersi de mümkündür. Hangisinin seçileceği problemin yapısına bağlıdır:

DurumDaha iyi seçimNeden
basit bir dizi: 1…n toplamı, faktöriyel, geri sayımdöngüyığın yok, derinlik sınırı yok, genellikle daha hızlı
ağaç biçimli veriler: iç içe listeler, klasörler, JSON, HTMLözyinelemekod verinin yapısını izler
böl ve yönet: ikili arama, birleştirmeli sıralama, hızlı sıralamaözyinelemederinlik yalnızca log₂ n kadardır
aynı alt problemler tekrar tekrar (Fibonacci)özyineleme + lru_cache ya da döngüher değer bir kez hesaplanır
derinlik binlerce düzeye ulaşabiliraçık yığınlı döngüRecursionError oluşmaz
Python
def sum_rec(n):
    return 0 if n == 0 else n + sum_rec(n - 1)


def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


print(sum_rec(100), sum_loop(100))
try:
    print(sum_rec(100_000))
except RecursionError:
    print('sum_rec(100000): RecursionError')
print(sum_loop(100_000))
Beklenen çıktı
5050 5050
sum_rec(100000): RecursionError
5000050000
Her özyinelemeli çağrı bir çerçeve ekler; bu yüzden sum_rec(100000) 100 000 çerçeve ister ve başarısız olur, döngünün ise hiçbirine ihtiyacı yoktur. Python kuyruk özyinelemesini iyileştirmez; fonksiyonu başka bir özyinelemeli biçimde yazmak da işe yaramaz.

Alıştırma

power(x, n) özyinelemeli fonksiyonunu yaz: xⁿ = x · xⁿ⁻¹ ve x⁰ = 1 (n, 0 veya daha büyük bir tam sayı). ** işlecini ve pow fonksiyonunu kullanma. Başlangıç kodundaki üç çağrıyı değiştirme.

Alıştırma · Python
def power(x, n):
    # base case: n == 0
    # recursive step: x * power(x, n - 1)
    pass


print(power(2, 10))
print(power(3, 4))
print(power(5, 0))
Beklenen çıktı
1024
81
1

Alıştırma

count_files(folder) fonksiyonu iç içe bir sözlükteki dosya sayısını döndürmeli: değeri sözlük olan anahtar bir alt klasör, değeri sayı olan anahtar bir dosyadır. Boş bir klasörde 0 dosya vardır.

Alıştırma · Python
tree = {
    'docs': {'cv.pdf': 120, 'letters': {'a.txt': 4, 'b.txt': 6}},
    'music': {},
    'photo.jpg': 900,
}


def count_files(folder):
    # a dict value is a subfolder, a number is a file
    pass


print(count_files(tree))
print(count_files(tree['docs']))
print(count_files(tree['music']))
Beklenen çıktı
4
3
0

Unutma

  • Özyinelemeli bir fonksiyon kendisini daha küçük bir girdiyle çağırır; bir temel duruma ve gerçekten ona yaklaşan bir adıma ihtiyaç duyar.
  • Her çağrı, çağrı yığınında kendi çerçevesini alır; sonuçlar çağrıların ters sırasıyla geri döner.
  • Ulaşılabilir bir temel durum olmadan yığın taşar: RecursionError (CPython’da varsayılan olarak yaklaşık 1000 düzey). return olmayan bir adım None verir.
  • Özyineleme ağaç biçimli verilere ve böl-yönet problemlerine uygundur: iç içe listeler, klasör ağaçları, ikili arama.
  • Tekrarlanan alt problemler → functools.lru_cache; basit ya da çok derin diziler → döngü.
Bu derste bir hata ya da yanlışlık mı gördün?

Kendini test et

12 soru. Her doğru cevap XP kazandırır.

Soru 1 / 12

Soru 1 / 12. Özyinelemeli bir fonksiyonun iki zorunlu parçası nelerdir?