Problem Context

Recursion is two things at once: a problem-decomposition technique that makes hard problems trivial, and the most common cause of stack overflows in production. The same code that elegantly traverses a tree in 6 lines will blow the stack on a deep linked list of 100,000 nodes. The skill is recognizing which class your problem belongs to before you write the first return.

In .NET, the default thread stack is 1MB and a typical recursive frame uses roughly 100-200 bytes — call it ~5,000-10,000 deep before StackOverflowException(which you cannot catch). That's plenty for a balanced binary tree of a million nodes (depth 20), and nowhere near enough for a degenerate one. This guide is the recursion mental model: when it's the right tool, when to convert to iteration, and when memoization turns exponential into polynomial.

🤔 Sound familiar?
  • You wrote a recursive Fibonacci and it took 30 seconds for n = 40
  • Your tree traversal works on test data but stack-overflows in production
  • You can't explain when to use recursion vs explicit stack vs iteration
  • You've never converted a tail-recursive function to a loop and don't know why .NET doesn't do it for you

This is the recursion playbook — base cases, memoization, tail calls, and when to bail out to an explicit stack.

Concept Explanation

Every recursive function is three things:

  • Base case — the smallest input where the answer is direct.
  • Recursive case — reduce the problem to smaller subproblems.
  • Combine — assemble the subproblem answers into the answer for this call.

If you can't articulate all three in one sentence each, you don't understand the recursion yet. Add memoization when subproblems overlap; convert to iteration when depth is unbounded.


flowchart LR
    P["Recursive problem?"] --> B{"Base case clear?"}
    B -->|no| FIX["Define base case<br/>(empty / size 1)"]
    B -->|yes| O{"Subproblems overlap?"}
    O -->|yes| M["Add memoization<br/>(or convert to DP)"]
    O -->|no| D{"Depth bounded by O(log n)?"}
    D -->|yes| R["Recursion is safe"]
    D -->|no| S["Convert to iteration<br/>+ explicit Stack&lt;T&gt;"]

    style R fill:#16a34a,color:#fff,stroke:#15803d
    style S fill:#dc2626,color:#fff,stroke:#b91c1c

Implementation

Step 1: The textbook example — and what makes it slow

// O(2^n) — recomputes Fib(n-2), Fib(n-3) ... exponentially many times
static long FibSlow(int n) =>
    n < 2 ? n : FibSlow(n - 1) + FibSlow(n - 2);

// FibSlow(40)  ≈ 1.5s
// FibSlow(50)  ≈ 90s     ← exponential blow-up

Step 2: Memoization — turn exponential into linear

static readonly Dictionary<int, long> _memo = new();

static long FibMemo(int n)
{
    if (n < 2) return n;
    if (_memo.TryGetValue(n, out var v)) return v;
    return _memo[n] = FibMemo(n - 1) + FibMemo(n - 2);
}
// FibMemo(50) → instant. FibMemo(10_000) → still hits stack overflow.

Step 3: Bottom-up iteration — no stack risk, no allocations

static long Fib(int n)
{
    if (n < 2) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) (a, b) = (b, a + b);
    return b;
}
// O(n) time, O(1) space, no recursion at all

Step 4: Recursion that's actually appropriate — divide & conquer

// Tree traversal: depth = O(log n) for a balanced tree → safe to recurse
public record Node(int Value, Node? Left = null, Node? Right = null);

public static int Sum(Node? n) =>
    n is null ? 0 : n.Value + Sum(n.Left) + Sum(n.Right);

// Mergesort: depth = O(log n) → safe
public static int[] MergeSort(int[] a)
{
    if (a.Length <= 1) return a;
    int mid = a.Length / 2;
    return Merge(MergeSort(a[..mid]), MergeSort(a[mid..]));
}

Step 5: Convert to iteration with an explicit stack

// Same logic, but the stack lives on the heap → no StackOverflowException
public static int Sum(Node? root)
{
    if (root is null) return 0;
    var stack = new Stack<Node>();
    stack.Push(root);
    int sum = 0;
    while (stack.Count > 0)
    {
        var n = stack.Pop();
        sum += n.Value;
        if (n.Right is not null) stack.Push(n.Right);
        if (n.Left  is not null) stack.Push(n.Left);
    }
    return sum;
}
// Now safe for trees with millions of nodes, even degenerate (linked-list-like)

Step 6: Tail recursion — and why .NET won't save you

// Tail-recursive: the recursive call is the LAST thing the function does
static long FactTail(int n, long acc = 1) =>
    n <= 1 ? acc : FactTail(n - 1, acc * n);

// In F#, Scala, or with C# 9 .tail IL prefix, this compiles to a loop.
// The C# compiler does NOT emit .tail by default. RyuJIT may optimize
// some tail calls but it&apos;s not guaranteed. For depth &gt; ~10k you must
// manually convert:

static long Fact(int n)
{
    long acc = 1;
    while (n > 1) { acc *= n; n--; }
    return acc;
}

Pitfalls

1. Missing or wrong base case. Off-by-one in the base case sends you to StackOverflowException via infinite recursion. Always test with the smallest possible input (empty, single element, depth 1).

2. Overlapping subproblems without memoization. Naive Fibonacci, naive coin-change, naive edit-distance — all are O(2^n) without memoization, O(n) or O(n·m) with it. If the same recursive call happens twice, memoize.

3. Recursing on unbounded depth. Linked lists, file-system trees, JSON from untrusted sources, deeply nested expression trees. All can be adversarial. Use an explicit Stack<T>.

4. Assuming C# does tail-call optimization. It doesn't reliably. StackOverflowException from a tail-recursive function will surprise you in production. Convert to a loop.

5. Cannot catch StackOverflowException. Since .NET 2.0 it terminates the process. You can't wrap recursion in try/catchas a safety net. Either bound the depth or don't recurse.

6. Mutable state captured by recursive closures. Recursive lambdas that capture a mutable variable cause races in parallel code and intermittent bugs in sequential code. Pass state as parameters.

Practical Takeaways

  • Use recursion when depth is provably O(log n) — balanced trees, divide & conquer, expression evaluators with bounded depth.
  • Use iteration + Stack<T> when depth could be O(n) — linked lists, untrusted JSON, file system walks.
  • Add memoization the moment you see the same subproblem twice. Often this means converting to bottom-up DP.
  • Never assume tail-call optimization in C#. Manually convert tail-recursive functions to loops if depth could be large.
  • Test recursion with empty input, single-element input, and a degenerate (worst-case-depth) input.
  • For tree algorithms exposed to user input, increase thread stack with new Thread(work, maxStackSize: 16_000_000) or convert to iteration.
  • Document the maximum supported depth in any public recursive API. "Works on small inputs" is a CVE waiting to happen.