Recursive Fonksiyonlarda Stack Overflow Önleme Teknikleri

Recursive fonksiyonlar zarif görünse de her çağrı call stack'e yeni bir frame ekler. Derin recursion hızla belleği doldurur ve program çöker. Bunu önlemek için birkaç kanıtlanmış yöntem var.

Tail Recursion Optimizasyonu

Tail recursion, fonksiyonun son işleminin kendini çağırması demektir. Bazı derleyiciler bunu döngüye dönüştürür ve stack'i temizler. C++17 ile constexpr fonksiyonlarda bu garantilidir.

1// Kötü: her çağrıda stack büyür
2int factorial_bad(int n) {
3if (n <= 1) return 1;
4return n * factorial_bad(n - 1);
5}
6
7// İyi: tail recursion
8int factorial_tail(int n, int acc = 1) {
9if (n <= 1) return acc;
10return factorial_tail(n - 1, n * acc);
11}

İkinci versiyonda hesaplama accumulator'da birikir. Derleyici bunu döngüye çevirebilir.

Memoization ile Tekrarlı Hesaplamayı Kesmek

Fibonacci gibi fonksiyonlarda aynı değerler defalarca hesaplanır. Sonuçları cache'lemek exponential karmaşıklığı polynomial'e düşürür.

1#include <unordered_map>
2#include <iostream>
3using namespace std;
4
5unordered_map<int, long long> memo;
6
7long long fibonacci(int n) {
8if (n <= 1) return n;
9if (memo.find(n)!= memo.end())
10return memo[n];
11
12memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
13return memo[n];
14}
15
16int main() {
17cout << fibonacci(50) << endl; // Hızlı çalışır
18return 0;
19}

Çıktı: 12586269025

Iterasyon ile Recursion'ı Değiştir

Eğer tail recursion derleyici tarafından optimize edilmeyecekse, basit bir döngüye geçiş en güvenli yoldur.

1// Recursive versiyonda stack overflow riski
2int power_recursive(int base, int exp) {
3if (exp == 0) return 1;
4return base * power_recursive(base, exp - 1);
5}
6
7// Iterative versiyonda güvenli
8int power_iterative(int base, int exp) {
9int result = 1;
10while (exp > 0) {
11result *= base;
12exp--;
13}
14return result;
15}

Stack Boyutunu Artırmak (Geçici Çözüm)

Linux'ta `ulimit -s` komutuyla stack boyutunu artırabilirsin, ama bu kök nedeni çözmez.

1ulimit -s 16384 // Stack'i 16 MB'a çıkart

Sık Yapılan Hata

Memoization kullanırken global map'i temizlemeyi unutmak, önceki test sonuçlarını etkileyebilir. Her test başında `memo.clear()` çağır veya fonksiyonu pure tutup cache'i parametre olarak geç.

Stack overflow'u sadece daha derin recursion çağrısıyla çözmek değil, algoritmanın kendisini sorgulamak gerekir. Tail recursion derleyici desteğine bağlıysa, memoization ve iterasyon daha güvenli seçeneklerdir.