C#'ta Recursion: Base Case, Call Stack, StackOverflowException ve Iterative'e Çevirmek

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır.

Önce Tahmin Et

Bookstore'un admin panelinde kategori menüsünün derinliğini hesaplayan recursive bir method var. Bir gün dışarıdan içe aktarılan bozuk bir kategori dosyası, her biri bir öncekinin alt kategorisi olan 1.000.000 seviyelik bir zincir üretiyor. Method'u çağıran kod try { ... } catch (Exception ex) { logger.LogError(ex, ...); } ile sarılmış.

Ne olur: exception yakalanıp log'a mı yazılır, istek 500 mü döner, yoksa başka bir şey mi? İkinci soru: macOS'ta bir .NET 10 uygulamasının ana thread'inde, hiçbir şey yapmayan bir method kendini kaç kez çağırabilir: 1.000 mi, 100.000 mi, 10 milyon mu?

Recursion'ın Anatomisi

Recursive bir fonksiyon problemi kendisinin daha küçük bir kopyasına indirger. Doğru çalışması için iki şart var: en az bir base case (artık kendini çağırmadan cevap verdiği durum) ve her çağrıda base case'e yaklaşmak. İkisinden biri eksikse fonksiyon hiç durmaz.

namespace Algorithms.Recursion;

public static class Basics
{
    public static long Factorial(int n)
    {
        ArgumentOutOfRangeException.ThrowIfNegative(n);
        if (n <= 1) return 1;            // base case
        return n * Factorial(n - 1);     // ilerleme: n her çağrıda küçülüyor
    }

    // divide and conquer: ikiye böl, iki yarıyı çöz, birleştir
    public static long Sum(ReadOnlySpan<int> values)
    {
        if (values.Length == 0) return 0;
        if (values.Length == 1) return values[0];
        int mid = values.Length / 2;
        return Sum(values[..mid]) + Sum(values[mid..]);
    }
}

Factorial n kez kendini çağırıyor ve çağrılar zincir gibi birbirini bekliyor; derinlik n. Sum ise array'i ikiye bölüp iki yarıyı ayrı ayrı topluyor: çağrı sayısı yine n civarında ama derinlik yalnızca log₂(n). 1 milyon elemanlı bir array için 20 seviye. Bu ikinci şekil divide and conquer'ın, yani merge sort'un, quick sort'un ve binary search'ün iskeleti; serinin sorting yazılarında tekrar karşımıza çıkacak. Recursion ile yazılmış bir algoritmanın complexity'sini recurrence ile çıkarmak Big-O ve Complexity serisinin "Koddan Time Complexity Çıkarmak" yazısında.

Call Stack: Her Çağrı Bir Frame

Bir method çağrıldığında runtime, thread'in stack'ine bir frame koyar: dönüş adresi, parametreler, local değişkenler ve kaydedilen register'lar. Method dönünce frame kaldırılır. Recursive bir çağrı zinciri, çağrı sayısı kadar frame'in üst üste birikmesi demek; en derindeki çağrı base case'e ulaşıp dönene kadar hiçbiri kaldırılamaz.

Bu yüzden recursion'ın bellek maliyeti O(derinlik): Factorial(n) için O(n), Sum için O(log n). Space complexity'nin bu tarafı Big-O ve Complexity serisinin "Space Complexity: Ek Bellek, Recursion Stack'i ve Allocation" yazısında. Debugger'daki Call Stack penceresi ise C# Temelleri serisinin "C# Hata Ayıklama: Breakpoint, Call Stack, Debug.Assert ve Derleyici Uyarıları" yazısında anlatıldı. Recursive bir method'da breakpoint'te durup o pencereye bakmak, frame'lerin birikmesini görmenin en hızlı yolu.

Thread stack'inin boyutu sabit ve heap'e göre çok küçük. macOS'ta ana thread'in stack'i shell'in ulimit -s değeri kadar; bu makinede 8.176 KB. Yeni bir Thread oluştururken maxStackSize ile boyut verebiliyorsun. ThreadPool thread'lerinin, yani ASP.NET Core isteklerinin ve Task.Run'ın çalıştığı thread'lerin boyutunu ise koddan değiştiremiyorsun.

.NET Gerçeği: StackOverflowException Yakalanamaz

Açılıştaki soruyu bir deneyle cevaplayalım. Bu kod her 50.000 çağrıda bir derinliği yazıyor ve bütün zinciri catch (Exception) ile sarıyor:

public static void Overflow()
{
    try
    {
        Dive();
    }
    catch (Exception ex) // hiç çalışmaz: stack overflow yakalanamaz
    {
        Console.WriteLine($"caught {ex.GetType().Name}");
    }
}

private static void Dive()
{
    _depth++;
    if (_depth % 50_000 == 0) Console.WriteLine($"depth {_depth:N0}");
    Dive();
}

$ dotnet Algorithms.Demos.dll overflow; echo "exit=$?"
depth 50,000
depth 100,000
Stack overflow.
Repeated 130648 times:
--------------------------------
   at Algorithms.Demos.RecursionDemo.Dive()
--------------------------------
   at Algorithms.Demos.RecursionDemo.Overflow()
   at Program.<Main>$(System.String[])
exit=134

catch bloğu hiç çalışmadı. Runtime "Stack overflow." yazıp stack trace'i bastı ve process'i sonlandırdı; çıkış kodu 134, yani SIGABRT (abort sinyali). Microsoft'un dokümanı da bunu açıkça söylüyor: StackOverflowException bir try/catch ile yakalanamaz ve process varsayılan olarak sonlandırılır. Bir web uygulamasında bu, o isteğin değil bütün process'in ölmesi demek: o anda işlenen diğer bütün istekler de gidiyor. Açılıştaki try/catch hiçbir şeyi kurtarmıyor; log'a da bir şey yazılmıyor.

İkinci sorunun cevabı da çıktıda: 8 MB'lık ana thread'de, hiçbir local değişkeni olmayan bir method yaklaşık 130.650 kez kendini çağırabildi; frame başına 64 byte civarı. Local değişkeni, parametresi ya da foreach enumerator'ı olan gerçek bir method'un frame'i daha büyük, sınır da o kadar düşük.

Fonksiyonel dillerden gelenlerin aklına tail call optimization gelir: recursive çağrı method'un son işiyse frame yeniden kullanılabilir ve stack büyümez. C#'ta buna güvenemezsin. C# derleyicisi IL'de (Intermediate Language) tail. öneki üretmiyor; JIT (Just-In-Time) derleyici optimize edilmiş kodda bazı çağrıları kendiliğinden tail call'a çevirebiliyor ama bu bir garanti değil, Debug derlemede hiç yok. Derinliği veriye bağlı bir recursion'ı "nasılsa tail call" diye bırakma.

Recursive'den Iterative'e: Kendi Stack'ini Tutmak

Recursion'ın yaptığı tek şey, "nerede kaldığını" call stack'te saklamak. Aynı bilgiyi heap'teki bir Stack<T>'te kendin saklarsan derinlik sınırı thread stack'inin 8 MB'ı olmaktan çıkar, process'in bütün belleği olur. Bookstore'un kapak görsellerini tutan klasörün toplam boyutunu iki şekilde hesaplayalım:

namespace Algorithms.Recursion;

public static class FolderSize
{
    public static long Recursive(string path)
    {
        long total = 0;
        foreach (string entry in Directory.EnumerateFileSystemEntries(path))
        {
            if (Directory.Exists(entry))
                total += Recursive(entry); // bu klasörde nerede kaldığımızı call stack hatırlıyor
            else
                total += new FileInfo(entry).Length;
        }
        return total;
    }

    public static long Iterative(string path)
    {
        long total = 0;
        Stack<string> pending = new(); // call stack frame'leri yerine heap'te kendi stack'imiz
        pending.Push(path);
        while (pending.TryPop(out string? folder))
        {
            foreach (string entry in Directory.EnumerateFileSystemEntries(folder))
            {
                if (Directory.Exists(entry))
                    pending.Push(entry);
                else
                    total += new FileInfo(entry).Length;
            }
        }
        return total;
    }
}

Dönüşümün tarifi her zaman aynı: recursive çağrının yerine "bunu sonra işle" diye stack'e push, döngünün başında pop. Toplam gibi sırası önemsiz işlerde bu kadar. Sıra önemliyse bir ayrıntı daha var. Admin panelindeki kategori menüsünü girintili bir listeye düzleştiren iki versiyon:

public sealed record MenuCategory(string Name, List<MenuCategory> Children)
{
    public MenuCategory(string name, params MenuCategory[] children) : this(name, new List<MenuCategory>(children)) { }
}

public static class CategoryMenu
{
    public static List<string> FlattenRecursive(MenuCategory root)
    {
        List<string> lines = [];
        Visit(root, 0);
        return lines;

        void Visit(MenuCategory category, int depth)
        {
            lines.Add(new string(' ', depth * 2) + category.Name); // base case: çocuk yoksa döngü hiç dönmez
            foreach (MenuCategory child in category.Children)
                Visit(child, depth + 1);
        }
    }

    public static List<string> FlattenIterative(MenuCategory root)
    {
        List<string> lines = [];
        Stack<(MenuCategory Category, int Depth)> pending = new();
        pending.Push((root, 0));
        while (pending.TryPop(out (MenuCategory Category, int Depth) item))
        {
            lines.Add(new string(' ', item.Depth * 2) + item.Category.Name);
            // ters sırayla push et ki ilk çocuk ilk çıksın: recursive versiyonla aynı sıra
            for (int i = item.Category.Children.Count - 1; i >= 0; i--)
                pending.Push((item.Category.Children[i], item.Depth + 1));
        }
        return lines;
    }
}

Recursive versiyonda depth bir parametre; iterative versiyonda her stack element'inin içinde taşınıyor. Frame'in içindeki her bilgi, iterative versiyonda stack'teki tuple'ın bir alanı oluyor. Çocukları ters sırayla push etmek, stack'in LIFO (Last In, First Out) olmasını telafi ediyor. Testler iki versiyonun aynı sonucu verdiğini ve iterative versiyonun 1.000.000 seviyelik zinciri sorunsuz gezdiğini doğruluyor:

[Fact]
public void Flatten_RecursiveAndIterative_SameOrder()
{
    MenuCategory menu = new("Books",
        new MenuCategory("Fiction", new MenuCategory("Science Fiction"), new MenuCategory("Classics")),
        new MenuCategory("Non-Fiction", new MenuCategory("Software", new MenuCategory(".NET"))));

    List<string> recursive = CategoryMenu.FlattenRecursive(menu);

    Assert.Equal(recursive, CategoryMenu.FlattenIterative(menu));
    Assert.Equal("      .NET", recursive[^1]);
    Assert.Equal(4, CategoryMenu.DepthRecursive(menu));
}

[Fact]
public void DepthIterative_MillionLevels_DoesNotOverflow()
{
    MenuCategory chain = CategoryMenu.Chain(1_000_000);

    Assert.Equal(1_000_000, CategoryMenu.DepthIterative(chain));
}

Aynı zinciri recursive DepthRecursive ile farklı stack boyutlarındaki thread'lerde çalıştıran demo, sınırın tamamen stack boyutuna bağlı olduğunu gösteriyor:

$ dotnet Algorithms.Demos.dll deep-menu 100000 1
iterative depth: 100,000
Stack overflow.
Repeated 11041 times:

$ dotnet Algorithms.Demos.dll deep-menu 100000 64
iterative depth: 100,000
recursive depth on a 64 MB thread: 100,000

$ dotnet Algorithms.Demos.dll deep-menu 1000000 64
iterative depth: 1,000,000
Stack overflow.
Repeated 699169 times:

1 MB'lık thread'de recursive versiyon 11.041 seviyede öldü; foreach enumerator'ı ve Math.Max ile bu method'un frame'i yaklaşık 95 byte. 64 MB'lık thread 100.000 seviyeyi geçti ama 1.000.000'de o da öldü. Iterative versiyon üçünde de çalıştı. Stack'i büyütmek sınırı yalnızca ileri itiyor; veriden gelen derinlikte asıl çözüm iterative'e çevirmek.

Kullanıcı Kontrollü Derinlik

Recursion'ın derinliği kullanıcının gönderdiği veriye bağlıysa, bu bir güvenlik sorunu: bir saldırgan çok derin bir input göndererek process'i öldürebilir, yani DoS (Denial of Service). Bu yüzden recursive parser'lar derinliğe bir sınır koyuyor. System.Text.Json'da JsonSerializerOptions.MaxDepth'in varsayılan değeri 0, bu da 64 seviye demek; aşılınca yakalanabilir bir JsonException fırlatılıyor:

public static void JsonDepth(int depth)
{
    string json = new string('[', depth) + new string(']', depth);
    try
    {
        JsonSerializer.Deserialize<JsonElement>(json);
        Console.WriteLine($"depth {depth}: ok");
    }
    catch (JsonException ex)
    {
        Console.WriteLine($"depth {depth}: {ex.GetType().Name}: {ex.Message}");
    }
}

depth 64: ok
depth 65: JsonException: The maximum configured depth of 64 has been exceeded. Cannot read next JSON array. Path: $ | LineNumber: 0 | BytePositionInLine: 64.

Kendi recursive kodunda aynı savunmayı iki şekilde kurabilirsin. Birincisi açık bir derinlik parametresi: Visit(child, depth + 1) içinde depth > MaxDepth ise anlamlı bir hata fırlat. Kategori menüsü için 20 seviye bile fazla; 21'inci seviyeyi gören import işlemi reddedilmeli. İkincisi runtime'ın kendi kontrolü: RuntimeHelpers.EnsureSufficientExecutionStack(), kalan stack alanı güvenli bir sınırın altına düştüğünde yakalanabilir bir InsufficientExecutionStackException fırlatıyor:

// recursive, ama process'i öldürmek yerine yakalanabilir bir exception ile duruyor
public static int DepthGuarded(MenuCategory category)
{
    System.Runtime.CompilerServices.RuntimeHelpers.EnsureSufficientExecutionStack();
    int deepest = 0;
    foreach (MenuCategory child in category.Children)
        deepest = Math.Max(deepest, DepthGuarded(child));
    return deepest + 1;
}

$ dotnet Algorithms.Demos.dll guarded 1000000
caught InsufficientExecutionStackException: Insufficient stack to continue executing the program safely. This can happen from having too many functions on the call stack or function on the stack using too much stack space.
process is still alive

Process bu sefer hayatta. Bu kontrolün her çağrıda küçük bir maliyeti var ve sınırın nerede olduğunu sen belirlemiyorsun; kullanıcıdan gelen veride açık bir MaxDepth, kendi iç algoritmalarında ise iterative versiyon daha iyi bir varsayılan.

Üretimde Dikkat

Derinliği verinin şekline bağlı her recursion'ı sorgula. Dengeli bir tree'de derinlik log n civarında kalır ve recursion güvenlidir. Ama aynı kod, sıralı veriyle kurulmuş dejenere bir tree'de ya da bozuk bir ParentId zincirinde n derinliğe çıkar. Serinin tree yazısında bunun gerçek bir örneğini göreceğiz. Test verinle değil, en kötü üretim verinle düşün.

Stack overflow'u log'larda arama. Process sonlandığı için uygulamanın kendi log'una hiçbir şey yazılmaz. İzi container'ın ya da servis yöneticisinin çıkış kodunda (134, SIGABRT) ve stderr'e basılan "Stack overflow." satırında bulursun. Kubernetes'te pod'un yeniden başlama sayısının sessizce artması tipik belirti.

Thread stack'ini büyütmek geçici bir yama. new Thread(..., maxStackSize) sınırı iter ama veri büyüdükçe sorun geri gelir; ThreadPool'da çalışan kodda bu seçeneğin hiç yok. Kalıcı çözüm iterative'e çevirmek ya da derinliği sınırlamak.

Recursion'ı kötü bir şey sanma. Tree ve graph üzerindeki algoritmaların çoğu recursive yazıldığında çok daha okunur; derinliğin log n ile sınırlı olduğunu bildiğin yerde (dengeli tree'ler, divide and conquer) recursive versiyon doğru seçim.

Sık Düşülen Tuzaklar

Base case'i eksik ya da ulaşılamaz yazmak. Factorial(-1)'i n == 0 base case'iyle yazarsan hiç durmaz; negatif girişi bu yüzden en başta reddediyoruz.

StackOverflowException'ı yakalamaya çalışmak. catch bloğu hiç çalışmaz; önlem ancak overflow'dan önce alınabilir: derinlik sınırı, EnsureSufficientExecutionStack ya da iterative versiyon.

Iterative'e çevirirken sırayı bozmak. Çocukları doğal sırayla push edersen stack onları ters sırayla çıkarır; menü tersine döner. Testte iki versiyonun çıktısını karşılaştırmak bu hatayı hemen yakalar.

Recursion boyunca paylaşılan mutable state. Recursive bir method'un dışarıdaki bir listeye yazması doğal, ama bir çağrının o listeyi değiştirip geri almayı unutması (özellikle backtracking'de) sonraki dalları bozar. İlerideki backtracking yazısında bunun "choose, explore, unchoose" şablonunu göreceğiz.

Küçük Bir Deneme

★☆☆ FlattenRecursive'e bir maxDepth parametresi ekle; aşılınca kategorinin adını ve yolunu içeren bir InvalidOperationException fırlatsın. 21 seviyelik bir zincirle test et.

★★☆ FolderSize.Iterative'i, her klasörün kendi toplam boyutunu da raporlayacak şekilde genişlet (Dictionary<string, long>). Bir klasörün toplamı ancak bütün alt klasörleri bittiğinde belli olur; bunu explicit stack ile nasıl yaparsın? İpucu: her klasörü stack'e iki kez koy.

★★★ Recursive bir merge sort'un derinliği log n. 1 MB'lık bir thread'de 100 milyon elemanlı bir array'i recursive merge sort ile sıralamak stack overflow'a yol açar mı? Önce hesapla, sonra küçük bir deneyle doğrula.

Recursion ve call stack'le linear yapılar bloğu bitiyor. Bir sonraki yazıda hashing'e geçiyoruz: kendi HashMap'imizi .NET'in Dictionary'si ile aynı iç yapıda, buckets ve entries array'leriyle yazıp collision'ları, load factor'ü ve kötü bir GetHashCode'un her şeyi nasıl O(n)'e düşürdüğünü göreceğiz.