ANKA MÜHENDİSLİKSincan / Ankara
Programlama • Orta

Özyineleme (Recursion) nedir?

Recursion

Bir fonksiyonun problemi daha küçük alt problemlere bölerek kendi kendini çağırması tekniği.

Özyineleme (recursion), bir fonksiyonun çözümünün bir parçası olarak kendisini çağırmasıdır. Problem her çağrıda biraz daha küçültülür ve sonunda doğrudan çözülebilecek kadar basit bir duruma ulaşılır. Bu basit duruma temel durum (base case) denir; temel durum olmayan ya da hiç ulaşılamayan bir özyinelemeli fonksiyon sonsuza kadar kendini çağırır.

Her fonksiyon çağrısı çağrı yığınında (call stack) yer kaplar. Çok derin özyineleme yığının dolmasına, yani stack overflow hatasına neden olabilir. Python varsayılan olarak özyineleme derinliğini sınırlar ve sınır aşıldığında RecursionError verir.

Özyineleme; ağaç yapılarında gezinme (ör. klasör içindeki tüm dosyaları listeleme), birleştirme sıralaması (merge sort), hızlı sıralama ve böl-ve-yönet algoritmaları için doğal bir çözümdür. Her özyinelemeli çözüm bir döngüyle de yazılabilir; hangisinin seçileceği okunabilirlik ve performansa göre belirlenir. Aynı alt problemlerin tekrar tekrar hesaplandığı durumlarda memoization (sonuçları önbelleğe alma) büyük hız kazandırır.

Örnek: Faktöriyel ve memoization ile Fibonacci

from functools import lru_cache

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

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

print(faktoriyel(5), fib(50))  # 120 12586269025

İpuçları

  • Özyinelemeli fonksiyon yazarken önce temel durumu yazın.
  • Aynı değeri defalarca hesaplıyorsanız memoization kullanın.