What is recursion? Explain base cases, the call stack and stack overflow in .NET, then write a recursive and an iterative version of a tree or folder walk in C#. When should you avoid recursion?

1. The two rules

1. Base case exists and is reachable for every input.
2. Progress: every recursive call moves strictly closer to the base case (smaller n, child node, shorter list).

Break rule 2 (cycles, n not decreasing, negative input to factorial) and you get infinite recursion.

2. What a stack frame contains

high addresses
+------------------------+
| Main frame             |
+------------------------+
| Walk(root) frame       |  return address, args, locals, saved registers
+------------------------+
| Walk(child) frame      |
+------------------------+
| Walk(grandchild) frame |  <- stack pointer moves down as calls nest
+------------------------+
|   ... guard page ...   |  touching this = stack overflow
low addresses

Async methods are different: await in a recursive async method stores state in heap-allocated state machines, but synchronous completion still runs nested on the stack, so very deep async recursion can still overflow.

3. Recursion to iteration: the general recipe

Any recursion can be turned into a loop with an explicit stack that lives on the heap:

recursive DFS:              iterative DFS:
Visit(node):                stack.Push(root)
  process(node)             while stack not empty:
  for child in children:      node = stack.Pop()
     Visit(child)             process(node)
                              push children (reverse order to keep same order)

Swap the Stack<T> for a Queue<T> and you get breadth-first order instead.

4. Tail recursion in C#

static long SumTo(long n, long acc = 0) => n == 0 ? acc : SumTo(n - 1, acc + n);

This is tail recursive (the call is the last action), and the x64 JIT sometimes turns such calls into jumps, but the C# language and runtime do not guarantee it (it differs by platform, debug versus release, and method shape). Never rely on it; write the loop.

5. Recursion complexity

Use a recurrence:

6. Defending against hostile depth

• System.Text.Json has JsonSerializerOptions.MaxDepth (default 64) so a deeply nested payload cannot blow your stack.
• RuntimeHelpers.EnsureSufficientExecutionStack() throws a catchable InsufficientExecutionStackException before you overflow; Roslyn and Json use this idea.
• Track visited nodes when data can contain cycles.
• Cap depth explicitly in business hierarchies (for example 50 levels).

7. Try it yourself

// 1) Watch the stack overflow (process will crash; run in a throwaway console app)
// static int Down(int n) => Down(n + 1);  Down(0);

// 2) Safe iterative folder size
long total = 0;
var pending = new Stack<string>();
pending.Push(Environment.GetFolderPath(Environment.SpecialFolder.UserProfile));
while (pending.Count > 0)
{
    var dir = pending.Pop();
    try
    {
        foreach (var f in Directory.EnumerateFiles(dir)) total += new FileInfo(f).Length;
        foreach (var d in Directory.EnumerateDirectories(dir)) pending.Push(d);
    }
    catch (UnauthorizedAccessException) { /* skip */ }
}
Console.WriteLine($"{total / 1_048_576} MB");

Note that Directory.EnumerateFiles(path, "*", SearchOption.AllDirectories) already does this, but writing it yourself shows the pattern.

public sealed record Category(int Id, string Name, List<Category> Children);

// Recursive: clear, depth = tree height
static void PrintRecursive(Category node, int depth = 0)
{
    Console.WriteLine($"{new string(' ', depth * 2)}{node.Name}");
    foreach (var child in node.Children)
        PrintRecursive(child, depth + 1);
}

// Iterative: same order, stack on the heap, cannot overflow the thread stack
static void PrintIterative(Category root)
{
    var stack = new Stack<(Category Node, int Depth)>();
    stack.Push((root, 0));
    while (stack.Count > 0)
    {
        var (node, depth) = stack.Pop();
        Console.WriteLine($"{new string(' ', depth * 2)}{node.Name}");
        for (int i = node.Children.Count - 1; i >= 0; i--)   // reverse to keep left-to-right order
            stack.Push((node.Children[i], depth + 1));
    }
}

// Walking up a parent chain safely: cycle detection and depth cap
static List<string> Breadcrumbs(int id, IReadOnlyDictionary<int, (string Name, int? ParentId)> all, int maxDepth = 50)
{
    var path = new List<string>();
    var visited = new HashSet<int>();
    int? current = id;
    while (current is int c)
    {
        if (!visited.Add(c)) throw new InvalidOperationException($"Cycle at category {c}");
        if (path.Count == maxDepth) throw new InvalidOperationException("Hierarchy too deep");
        var (name, parent) = all[c];
        path.Add(name);
        current = parent;
    }
    path.Reverse();
    return path;
}