Rekursiyonu Neredeyse Bes Yasindaymis Gibi Anlatiyoruz

Rekürsyon, haftalarca kafanızı karıştırdıktan sonra aniden oturan kavramlardan biridir. Bunu öğrenciler ve junior geliştiricilerle düzinelerce kez gördüm. Bir gün hiç anlam ifade etmiyor, ertesi gün her şey yerine oturuyor.

Bu "tık" anının şimdi yaşanmasını sağlamaya çalışayım.

Düşünmenin En Basit Yolu

Bir insan kuyruğunda durduğunuzu ve birinin size "bu kuyrukta kaç kişi var?" diye sorduğunu düşünün. Tüm kuyruğu göremiyorsunuz çünkü köşeyi dönüyor. Arkanızdaki kişinin omzuna dokunup soruyorsunuz: "Kendiniz dahil arkanızda kaç kişi var?"

O kişi de aynı şeyi yapıyor — bir sonraki kişiye dokunup aynı soruyu soruyor. Bu, en son kişi arkasına bakıp kimseyi görmeyene ve "sadece ben — bir kişi" deyene kadar devam eder.

Sonra her cevap kuyrukta yukarı doğru akar. Önlerindeki kişi "iki" der (kendileri artı bir). Sonraki "üç" der. Bu dalga size kadar ulaşır ve kendinizi ekleyerek son cevabı alırsınız.

İşte rekürsyon budur. Büyük bir problemi, birine aynı problemin biraz daha küçük versiyonunu çözmesini isteyerek çözersiniz.

Kıramayacağınız İki Kural

Her rekürsif fonksiyonun tam olarak iki şeye ihtiyacı vardır ve herhangi birini kaçırırsanız kodunuz muhteşem şekillerde bozulur.

Kural 1: Temel Durum

Temel durum, rekürsyonun durduğu yerdir. Başka birine sormadan bildiğiniz cevaptır. Kuyruk örneğimizde, "sadece ben — bir" diyen son kişidir.

Temel durum olmadan fonksiyonunuz kendini sonsuza kadar çağırır. Aslında sonsuza kadar değil — bellek bittiğinde stack overflow hatası ile çöker. Bunu itiraf etmek istediğimden fazla yaptım.

Kural 2: Rekürsif Durum

Rekürsif durum, fonksiyonun kendini daha küçük veya daha basit bir girdiyle çağırdığı yerdir. Her çağrı temel duruma doğru ilerleme kaydetmelidir.

Basit Başlayalım: Faktöriyel

5'in faktöriyeli (5! olarak yazılır) 5 x 4 x 3 x 2 x 1 = 120'dir. Bunu şöyle ifade edebilirsiniz: 5! = 5 x 4!, ve 4! = 4 x 3!, ta ki 1! = 1 olana kadar.

def factorial(n):
    if n <= 1:        # Temel durum: 1! = 1 biliyoruz
        return 1
    return n  factorial(n - 1)  # Rekürsif durum: n! = n  (n-1)!

factorial(4) adım adım takip edelim çünkü takip etmek rekürsyonu anlamanın en iyi yoludur:

factorial(4)
  = 4 * factorial(3)
  = 4  (3  factorial(2))
  = 4  (3  (2 * factorial(1)))
  = 4  (3  (2 * 1))          # Temel duruma ulaşıldı!
  = 4  (3  2)
  = 4 * 6
  = 24

Fonksiyonun kendini çağırmaya devam ederek ertelenmiş çarpımlar zinciri oluşturduğunu görüyor musunuz? Sonunda temel duruma ulaştığında, tüm çarpımlar ters sırada çalışır.

Daha İlginç Bir Örnek: Üs Fonksiyonu

x'in n'inci kuvvetini hesaplama:

def power(x, n):
    if n == 0:            # Temel durum: herhangi bir şeyin 0. kuvveti 1'dir
        return 1
    if n < 0:
        return 1 / power(x, -n)
    return x * power(x, n - 1)

Bu çalışır ama O(n)'dir. Akıllıca bir gözlemle daha iyi yapabiliriz: x^10 = (x^5)^2. Bu her adımda işi yarıya indirir:

def fast_power(x, n):
    if n == 0:
        return 1
    if n < 0:
        return 1 / fast_power(x, -n)
    if n % 2 == 0:
        half = fast_power(x, n // 2)
        return half * half
    return x * fast_power(x, n - 1)

Şimdi O(log n). fast_power(2, 1000) için 1000 yerine yaklaşık 10 çağrı. Aynı sonuç, dramatik şekilde daha az iş.

Pratik Bir Örnek: Dizin Ağacında Arama

Rekürsyon sadece akademik değildir. İşte gerçek projelerde kullanabileceğiniz bir şey — iç içe dizinlerde dosya arama:

import os
def find_file(directory, target):
    for item in os.listdir(directory):
        path = os.path.join(directory, item)
        if item == target:
            return path
        if os.path.isdir(path):
            result = find_file(path, target)
            if result:
                return result
    return None

Bu, verinin kendisi rekürsif olduğu için rekürsyonun tamamen doğal hissettirdiği bir durumdur — dizinler dizinleri içerir.

Rekürsif Düşünme: Anahtar İçgörü

Rekürsyonun en zor kısmı sözdizimi değil — rekürsif düşünmeyi öğrenmektir. İşte yapmanız gereken zihinsel değişim:

Tüm yürütmeyi kafanızda takip etmeye çalışmayı bırakın.

Bunun yerine rekürsyona güvenin. Rekürsif çağrının doğru çalıştığını varsayın ve sadece bir seviyeye odaklanın:

1. Temel durumum ne? Bu problemin en basit versiyonu ne? 2. Biraz daha küçük problemin cevabı elimde olsaydı, mevcut problemi çözmek için nasıl kullanırdım? 3. Rekürsif çağrım gerçekten problemi daha küçük yapıyor mu?

Bu "inanç sıçraması" rekürsif fonksiyonları güvenle yazmanın sırrıdır.

Klasik Rekürsif Problemler

Fibonacci Sayıları

Her sayı önceki ikisinin toplamıdır: 0, 1, 1, 2, 3, 5, 8, 13, 21...

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

Bu zarif ama korkunç derecede yavaştır — O(2^n). fib(40) bir milyardan fazla çağrı yapar çünkü aynı değerleri tekrar tekrar hesaplar.

Memoization ile Fibonacci

Düzeltme basit — zaten hesapladığınız değerleri hatırlayın:

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

Şimdi O(n). Aynı mantık, aynı rekürsif yapı, ama her değer tam olarak bir kez hesaplanır. Bu teknik — memoization — bir programcının cephaneliğindeki en güçlü araçlardan biridir.

İkili Arama

def binary_search(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low > high:
        return -1
    
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)

Her çağrı arama alanını yarıya indirir — O(log n).

Rekürsyonu Ne Zaman KULLANMAMALI

Ders kitaplarının nadiren vurguladığı şey: rekürsyon her zaman en iyi seçim değildir.

Rekürsyonu kullanın:

• Veri yapısı doğal olarak rekürsif olduğunda (ağaçlar, graflar, iç içe nesneler)
• Problem alt problemlere temiz bölündüğünde (böl ve fethet)
• Kod netliği önemliyse ve rekürsyon derinliği yönetilebilirse

Rekürsyondan kaçının:

• Basit döngü aynı şeyi daha net yapabiliyorsa
• Rekürsyon çok derin olabiliyorsa (Python limiti 1000)
• Performans kritikse ve fonksiyon çağrı maliyeti önemliyse

Ağaç Yapılarında Rekürsyon

Ağaçlar rekürsyonun gerçekten parladığı yerdir çünkü ağaç kendisi rekürsif bir veri yapısıdır.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def tree_sum(node):
    if node is None:
        return 0
    return node.val + tree_sum(node.left) + tree_sum(node.right)
def tree_height(node):
    if node is None:
        return 0
    return 1 + max(tree_height(node.left), tree_height(node.right))

tree_height fonksiyonunu rekürsyon olmadan yazmayı deneyin. Yapılabilir ama kod çok daha karmaşık olur. Bu, rekürsyonun en iyi hali — karmaşık bir geçişi sadece üç satırda ifade etmek.

Sonuç

Rekürsyon bir kodlama tekniği olduğu kadar bir düşünme aracıdır. Size büyük problemleri küçük parçalara ayırmayı, temel durumları belirlemeyi ve küçük problemleri doğru çözmenin büyüğünü çözeceğine güvenmeyi öğretir.

Basit örneklerle başlayın — faktöriyel, üs, Fibonacci. Kağıt üzerinde elle takip edin. Bunlar doğal geldiğinde ağaçlara ve graflara geçin. Takılırsanız unutmayın: anahtar her çağrıyı kafanızda takip etmek değil. Rekürsyona güvenin, bir seviyeye odaklanın ve temel durumunuzun doğru olduğundan emin olun.

Bir kez oturduğunda, her yerde rekürsif kalıplar görmeye başlayacaksınız. Ve programlama o zaman gerçekten eğlenceli hale gelir.