Algorithms & DSIntermediate

Recursion: When It's Elegant, When It's a Stack Overflow

Base/recursive/combine, memoization vs iteration, why .NET doesn't reliably tail-call optimize, and converting recursion to an explicit Stack<T> for adversarial depth.

By Amit UpadhyayPublished 25 Dec 2025Updated 11 Oct 202612 minArticle 5 of 7 in Algorithms & DS

Safe recursion over a category tree: every call has a base case and makes progress, a visited set detects cycles in imported data, an explicit stack replaces the call stack for unbounded depth, and memoisation removes repeated work.

On this page

The idea at a glance

The problem

When

The data is naturally nested: category trees, comment threads, folders, JSON, expression trees

The obvious move

A recursive function that assumes the data is a well-formed, shallow tree

Fails because

Real data has cycles and surprising depth; each call uses stack space, and running out crashes the process

The fix

Recursion works by

Clear base cases, a visited set when data can contain cycles, an explicit stack when depth is unbounded, and memoisation when the same subproblem repeats

At the cost of

A little more code than the elegant version, and memory for the visited set or memo table

The scenario every mode follows

“Build the menu under “Home & Garden”.”

The store’s catalogue service, which builds category menus from data imported from suppliers
~40,000 categories; nesting usually 4–6 levels

Where the obvious approach breaks

1 category pointing at its own ancestor crashed the process

If you recursive walk with no cycle check.

A supplier import set “Outdoor Lighting” as the parent of “Garden”, which was already its ancestor. The recursive walk went round the loop until the stack overflowed. In .NET a stack overflow cannot be caught, so the whole catalogue service terminated, restarted and crashed again on the next menu request.

Elegant Until the Data Disagrees

A catalogue service built category menus with a six-line recursive function. It worked for years, until a supplier import made “Outdoor Lighting” the parent of “Garden”, which was already its ancestor. The walk went round the loop until the stack overflowed, and because .NET cannot catch a stack overflow, the process died, restarted, and died again on the next menu request.

Recursion is the clearest way to express nested problems, and it quietly trusts the data to be shallow and acyclic. The skill is knowing when that trust holds. Below is how to write recursive functions that stop, when to switch to an explicit stack, how memoisation turns exponential work into linear, and why a depth limit is not a fix for a cycle.

If recursion has crashed your service

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

Base Cases, Progress and the Call Stack

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

Recursion, Explicit Stacks and Memoisation

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;
}

How Recursive Code Fails

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.

When I Use Recursion

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.

Decisions and trade-offs

The choices this rests on

Each choice has a reason and a point where it stops being right. The Test questions are built from these.

1
Write the base case first, and make sure every call moves towards it
Recursion is correct when the smallest case is handled and each call works on something strictly smaller.
Stops being right when
Never. If you cannot say what gets smaller, the function may not stop.
2
Track visited nodes whenever the data could contain cycles
Imported, user-edited or linked data can loop. A visited set turns infinite recursion into a detected, reportable problem.
Stops being right when
The structure is built by your own code in a way that cannot form cycles, such as a parsed expression.
3
Use an explicit stack when depth is not bounded by design
Thread stacks are small, often around 1 MB, and Python stops at a default depth of 1,000. A heap-allocated stack grows as needed.
Stops being right when
Depth is small and bounded, such as a balanced tree, where recursion is clearer.
4
Memoise when the same subproblem is solved repeatedly
Naive recursive Fibonacci makes exponentially many calls; caching each result makes it linear. The same applies to many search and pricing problems.
Stops being right when
Subproblems never repeat, so the cache only costs memory.

In production

Running it once real traffic arrives

What to watch, what it costs at the scenario’s volume, and what to check first when something goes wrong.

What to watch

Cycles detected in imported data
Shows bad data being stopped early.
Tracked; rejected at import
Maximum tree depth seen
Sudden depth suggests bad data or a missing base case.
Within expectations
Process crashes with stack overflow
They take the whole service down.
0

What it costs

Visited setone id per category visitedsmall

Explicit stackheap memory proportional to depthsmall

Outage avoideda crash loop on every menu requestthe real saving

TotalA few lines of code and a little memory

When it breaks

The service crashes with a stack overflow

CheckIs there a cycle in the data, or unusual depth?
FixFind the cycle with an iterative walk, fix the data, and add cycle checks to the import

A recursive calculation is very slow

CheckAre the same arguments being computed many times?
FixMemoise by argument, or rewrite bottom-up

In the real world

The supplier import that looped

A composite of common hierarchy bugs. Details are illustrative.

Before

A cycle in imported category data overflowed the stack, and the catalogue service crash-looped.

What they built

A visited set in the walk
An explicit stack instead of recursion
Cycle checks when imports change parents
Tests with cyclic and very deep data

What changed

No more crash loops
Bad imports rejected with a clear reason

The lessonRecursion trusts the data. When the data comes from outside, check it or stop trusting it.

When not to use it

Reach for something else when

If you needUse instead

Very deep or unbounded structuresAn explicit stack or queue

Simple loops over a listA loop

Hierarchies stored in a databaseA recursive CTE with a depth or cycle guard

Check yourself

Two questions before you move on

Answer in your head first, then open the answer.

Why did the catalogue service keep crashing after restarts?

The cyclic data was still there, and a stack overflow in .NET cannot be caught, so every menu request killed the process again.

Why is a depth limit not enough?

It stops the crash but hides the cycle, producing repeated nodes instead of reporting the bad data.

Where this leads

Trees

Most recursive code walks a tree. Knowing tree shapes tells you how deep it can go.

Next topic →

Next: See →

recursion algorithms memoization tail-call csharp

← PreviousSorting in 2026: Introsort, Stability, and When to Reach for Radix Next →Dynamic Programming: State, Recurrence, Base Case, Order

Continue reading

All Algorithms & DS articles →

Algorithms & DS14 min