Özyineleme (recursion) ile iterasyon arasındaki farklar nelerdir?
Cevap
Özyineleme, bir fonksiyonun problemi küçülterek kendini çağırmasıdır. Her özyinelemeli fonksiyonda iki parça olmalıdır:
- Taban durumu (base case): özyinelemeyi durdurur.
- Özyinelemeli adım: problemi taban duruma yaklaştırır.
def factorial_rec(n):
if n <= 1: # taban durumu
return 1
return n * factorial_rec(n - 1)
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result| Özyineleme | İterasyon | |
|---|---|---|
| Bellek | Her çağrı için call stack çerçevesi, O(derinlik) | Genelde O(1) |
| Risk | Stack overflow (Python'da varsayılan limit ~1000) | Sonsuz döngü |
| Okunabilirlik | Ağaç, graf, böl-ve-yönet için doğal | Doğrusal işlemler için doğal |
| Performans | Fonksiyon çağrısı maliyeti | Genelde biraz daha hızlı |
Notlar
- Her özyineleme, açık bir stack kullanılarak iterasyona çevrilebilir.
- Tail call optimization: son işlem özyinelemeli çağrıysa bazı diller (Scheme, bazı derleyiciler) stack büyütmez; Python ve Java bunu yapmaz.
- Örtüşen alt problemlerde (Fibonacci) naif özyineleme üstel süre alır; memoization gerekir.
- Ağaç gezinme, permütasyon üretme, backtracking gibi problemlerde özyineleme kodu çok daha sade yapar.
İlgili Algoritmalar & Veri Yapıları soruları
- Binary search'ün zaman karmaşıklığı nedir ve neden?
- Two Sum: toplamı hedefe eşit olan iki elemanın indekslerini bulun.
- Bir parantez dizisinin geçerli olup olmadığını kontrol edin: "({[]})"
- Tek yönlü bağlı listeyi ters çevirin.
- BFS ve DFS arasındaki fark nedir? Hangisini ne zaman kullanırsınız?
- get ve put işlemleri O(1) olan bir LRU Cache tasarlayın.
Bu konuda başka bir soru biliyor musun?
Mülakatta karşılaştığın soruları ekle, onaylandıktan sonra yayına alınsın.