Recursion

Recursion is when a method calls itself to solve a smaller version of the same problem. Every recursive solution needs a base case (stop condition) and a recursive case (the self-call).

Factorial

public static long Factorial(int n)
{
    if (n <= 1) return 1;         // base case
    return n * Factorial(n - 1);  // recursive case
}

Console.WriteLine(Factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)

Fibonacci

// Simple recursive (O(2^n) — very slow for large n)
public static int Fib(int n)
{
    if (n <= 1) return n;
    return Fib(n - 1) + Fib(n - 2);
}

// Memoized version (O(n) — much faster)
public static long FibMemo(int n, Dictionary<int, long>? memo = null)
{
    memo ??= new Dictionary<int, long>();
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];

    memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
    return memo[n];
}

Console.WriteLine(FibMemo(50)); // 12586269025

How the Call Stack Works

Each recursive call adds a frame to the call stack. Too many calls cause a StackOverflowException:

Factorial(4) → waits for Factorial(3)
  Factorial(3) → waits for Factorial(2)
    Factorial(2) → waits for Factorial(1)
      Factorial(1) → returns 1    ← base case hit
    Factorial(2) → returns 2
  Factorial(3) → returns 6
Factorial(4) → returns 24

When to Use Recursion

Good for: Tree traversal, divide-and-conquer, backtracking problems, anything with a naturally recursive structure.

Avoid when: Simple iteration works. Recursion has overhead from stack frames and can cause stack overflows for deep recursion. C# does not optimize tail recursion.