Recursion

A recursive method solves a problem by calling itself on a smaller version of the same problem, until it reaches a case simple enough to answer directly. Recursion is the natural fit for nested structures — folders inside folders, comments with replies, trees — and for divide-and-conquer algorithms.

Base case and recursive case

Every recursive method needs two parts: a base case that stops the recursion, and a recursive case that moves towards it. Factorial is the classic example: 5! = 5 × 4!, and 1! = 1.

Console.WriteLine(Factorial(5));
Console.WriteLine(Factorial(20));

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

Output

120
2432902008176640000

Each call waits for the one below it: Factorial(5) needs Factorial(4), which needs Factorial(3), down to Factorial(1), which answers immediately. Then the results multiply back up the chain.

Watching the calls

Printing with indentation shows how calls stack up and then return:

SumTo(4, 0);

static int SumTo(int n, int depth)
{
    string indent = new string(' ', depth * 2);
    Console.WriteLine($"{indent}SumTo({n})");
    int result = n == 0 ? 0 : n + SumTo(n - 1, depth + 1);
    Console.WriteLine($"{indent}= {result}");
    return result;
}

Output

SumTo(4)
  SumTo(3)
    SumTo(2)
      SumTo(1)
        SumTo(0)
        = 0
      = 1
    = 3
  = 6
= 10

Recursion on strings and arrays

Console.WriteLine(Reverse("recursion"));
Console.WriteLine(DigitSum(98765));
Console.WriteLine(IsPalindrome("level"));

static string Reverse(string s) =>
    s.Length <= 1 ? s : Reverse(s[1..]) + s[0];

static int DigitSum(int n) =>
    n < 10 ? n : n % 10 + DigitSum(n / 10);

static bool IsPalindrome(string s) =>
    s.Length <= 1 || (s[0] == s[^1] && IsPalindrome(s[1..^1]));

Output

noisrucer
35
True

Nested structures

Recursion shines when data contains smaller copies of itself. Here a category tree of any depth is printed and counted with two short methods:

var root = new Category("Shop",
[
    new("Books", [new("Fiction", []), new("Science", [new("Physics", []), new("Biology", [])])]),
    new("Music", [new("Vinyl", [])]),
]);

Print(root, 0);
Console.WriteLine($"Total categories: {Count(root)}");

static void Print(Category c, int level)
{
    Console.WriteLine(new string(' ', level * 2) + c.Name);
    foreach (Category child in c.Children)
        Print(child, level + 1);
}

static int Count(Category c)
{
    int total = 1;
    foreach (Category child in c.Children)
        total += Count(child);
    return total;
}

record Category(string Name, List<Category> Children);

Output

Shop
  Books
    Fiction
    Science
      Physics
      Biology
  Music
    Vinyl
Total categories: 8

Writing this with loops alone would need you to manage your own stack. (The record type used for Category is explained in lesson 40.)

Divide and conquer: binary search

Binary search finds a value in a sorted array by checking the middle and recursing into the half that could contain it. Each step halves the work:

int[] sorted = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
Console.WriteLine(Find(sorted, 23, 0, sorted.Length - 1));
Console.WriteLine(Find(sorted, 7, 0, sorted.Length - 1));

static int Find(int[] a, int target, int lo, int hi)
{
    if (lo > hi) return -1;                 // not found
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    return a[mid] < target
        ? Find(a, target, mid + 1, hi)
        : Find(a, target, lo, mid - 1);
}

Output

5
-1

The cost of naive recursion

The Fibonacci sequence (each number is the sum of the two before) has an obvious recursive definition, but it recomputes the same values again and again — the number of calls grows exponentially:

int calls = 0;
Console.WriteLine(Fib(25));
Console.WriteLine($"{calls:N0} calls");

int Fib(int n)
{
    calls++;
    return n < 2 ? n : Fib(n - 1) + Fib(n - 2);
}

Output

75025
242,785 calls

Memoization — remembering results you've already computed — fixes it:

var memo = new Dictionary<int, long>();
Console.WriteLine(Fib(90));
Console.WriteLine($"{memo.Count} values cached");

long Fib(int n)
{
    if (n < 2) return n;
    if (memo.TryGetValue(n, out long cached)) return cached;
    long result = Fib(n - 1) + Fib(n - 2);
    memo[n] = result;
    return result;
}

Output

2880067194370816120
89 values cached

Stack overflow

Every call uses some memory on the call stack. Recursion that never reaches its base case — or simply goes very deep, like hundreds of thousands of levels — exhausts the stack and the process crashes with a StackOverflowException. Unlike other exceptions, it can't be caught. C# doesn't guarantee tail-call optimisation, so for long linear processes (walking a list of a million items) use a loop instead.

A good rule: use recursion when the problem is naturally nested or halves at each step; use loops for simple repetition.

Try it yourself

Write a recursive Power(x, n) that uses xⁿ = (x^n/2)² to need only about log₂(n) calls.

Output

1024
1594323
1

PreviousOverloading & Local Functions NextArrays