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.
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).
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(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.
Ç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.
return en üstteki çerçeveyi kaldırır.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: 24Yığı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:
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.
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.
Burada
- F(n)
- n’inci Fibonacci sayısı
Adım iki terim geriye baktığı için iki temel durum gerekir.
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]
Ö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
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:
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.
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ı.
Boş aralık
lo > hiise değer yoktur:-1döndür (temel durum).Ortadaki eleman
mid = (lo + hi) // 2;items[mid] == targetisemiddöndür (temel durum).Sağ yarı
items[mid] < targetise[mid + 1..hi]aralığında ara.Sol yarı
Aksi hâlde
[lo..mid − 1]aralığında ara.
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
Etkileşimli
Ö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.
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:
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:
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
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:
| Durum | Daha iyi seçim | Neden |
|---|---|---|
| basit bir dizi: 1…n toplamı, faktöriyel, geri sayım | dö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 | özyineleme | kod verinin yapısını izler |
| böl ve yönet: ikili arama, birleştirmeli sıralama, hızlı sıralama | özyineleme | derinlik 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şabilir | açık yığınlı döngü | RecursionError oluşmaz |
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
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.
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.
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).returnolmayan bir adımNoneverir. - Ö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ü.