ZetCode

C# recursion

last modified November 15, 2026

This article shows how to write recursive methods in C#. We cover base cases, memoization, divide and conquer, recursion over trees, backtracking, stack overflows, and converting recursion to iteration.

Recursion is a technique in which a method calls itself. A recursive method solves a problem by reducing it to a smaller instance of the same problem. Every recursive method needs two parts: a base case, which returns a result directly, and a recursive case, which calls the method with an argument that moves closer to the base case. Without a reachable base case, the method calls itself until the program runs out of stack space.

Each call gets its own stack frame with its parameters and local variables. The frames pile up until the base case is reached, and then the calls return in reverse order. Recursion is a natural fit for problems that are recursive by nature: tree and graph traversal, divide and conquer algorithms, parsing of nested structures, and generating combinations.

Factorial

The factorial of n is the product of all positive integers up to n. It has a recursive definition: n! = n * (n - 1)! and 0! = 1.

Program.cs
for (int i = 0; i <= 5; i++)
{
    Console.WriteLine($"{i}! = {Factorial(i)}");
}

Console.WriteLine($"20! = {Factorial(20)}");
Console.WriteLine($"20! = {FactorialLoop(20)}");

static long Factorial(int n)
{
    if (n <= 1)
    {
        return 1;
    }

    return n * Factorial(n - 1);
}

static long FactorialLoop(int n)
{
    long result = 1;

    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }

    return result;
}

We compute factorials recursively and with a loop.

if (n <= 1)
{
return 1;
}

return n * Factorial(n - 1);

The if statement is the base case. The recursive case multiplies n by the factorial of n - 1. The call Factorial(4) expands to 4 * 3 * 2 * Factorial(1).

static long FactorialLoop(int n)

The iterative version gives the same result. In C#, a loop is usually faster than recursion because it avoids the cost of a method call per step. The value 20! is the largest factorial that fits into long; for larger values, see the BigInteger tutorial.

$ dotnet run
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
20! = 2432902008176640000
20! = 2432902008176640000

Fibonacci and memoization

A recursive method that calls itself more than once can repeat the same work many times. Memoization stores results that were already computed and reuses them.

Program.cs
using System.Diagnostics;

int calls = 0;

var sw = Stopwatch.StartNew();
long f1 = Fib(35);
sw.Stop();
Console.WriteLine($"Fib(35) = {f1}, {calls:N0} calls, {sw.ElapsedMilliseconds} ms");

calls = 0;
var memo = new Dictionary<int, long>();

sw.Restart();
long f2 = FibMemo(35);
sw.Stop();
Console.WriteLine($"FibMemo(35) = {f2}, {calls:N0} calls, {sw.ElapsedMilliseconds} ms");

Console.WriteLine($"FibMemo(90) = {FibMemo(90)}");

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

long FibMemo(int n)
{
    calls++;

    if (n < 2)
    {
        return n;
    }

    if (memo.TryGetValue(n, out long cached))
    {
        return cached;
    }

    long result = FibMemo(n - 1) + FibMemo(n - 2);
    memo[n] = result;

    return result;
}

We compute the 35th Fibonacci number with plain recursion and with a cache. Both methods are local functions, so they can use the calls counter and the memo dictionary from the enclosing code.

return n < 2 ? n : Fib(n - 1) + Fib(n - 2);

Each call makes two more calls, so the number of calls grows exponentially. Fib(n - 1) and Fib(n - 2) compute largely the same values again.

if (memo.TryGetValue(n, out long cached))
{
return cached;
}

long result = FibMemo(n - 1) + FibMemo(n - 2);
memo[n] = result;

The memoized version computes each value only once and stores it in a dictionary. The number of calls drops from almost 30 million to 69, and the method computes FibMemo(90) instantly. The timings depend on the machine.

$ dotnet run
Fib(35) = 9227465, 29,860,703 calls, 87 ms
FibMemo(35) = 9227465, 69 calls, 1 ms
FibMemo(90) = 2880067194370816120

Towers of Hanoi

The Towers of Hanoi puzzle is a classic example of a problem that is hard to solve iteratively but has a short recursive solution. We move a stack of disks from one peg to another; only one disk can be moved at a time and a larger disk may never lie on a smaller one.

Program.cs
int moves = 0;

Hanoi(3, 'A', 'C', 'B');
Console.WriteLine($"{moves} moves");

void Hanoi(int n, char from, char to, char via)
{
    if (n == 0)
    {
        return;
    }

    Hanoi(n - 1, from, via, to);
    moves++;
    Console.WriteLine($"move disk {n} from {from} to {to}");
    Hanoi(n - 1, via, to, from);
}

We solve the puzzle for three disks.

Hanoi(n - 1, from, via, to);
moves++;
Console.WriteLine($"move disk {n} from {from} to {to}");
Hanoi(n - 1, via, to, from);

To move n disks, we move the top n - 1 disks out of the way to the spare peg, move the largest disk to the target, and move the n - 1 disks on top of it. Each of the two recursive calls solves a smaller puzzle. The solution takes 2n - 1 moves.

$ dotnet run
move disk 1 from A to C
move disk 2 from A to B
move disk 1 from C to B
move disk 3 from A to C
move disk 1 from B to A
move disk 2 from B to C
move disk 1 from A to C
7 moves

Recursion over trees

Tree structures are recursive: each node contains child nodes that are trees themselves. Methods that process trees are therefore naturally recursive.

Program.cs
var root = new Node("src",
[
    new("Program.cs"),
    new("Models",
    [
        new("User.cs"),
        new("Order.cs"),
    ]),
    new("Services",
    [
        new("Mail",
        [
            new("SmtpSender.cs"),
        ]),
        new("Billing.cs"),
    ]),
]);

Print(root, 0);
Console.WriteLine($"files: {CountFiles(root)}, depth: {Depth(root)}");

static void Print(Node node, int level)
{
    Console.WriteLine($"{new string(' ', level * 2)}{node.Name}");

    foreach (var child in node.Children)
    {
        Print(child, level + 1);
    }
}

static int CountFiles(Node node) =>
    node.Children.Count == 0 ? 1 : node.Children.Sum(CountFiles);

static int Depth(Node node) =>
    1 + (node.Children.Count == 0 ? 0 : node.Children.Max(Depth));

record Node(string Name, List<Node> Children)
{
    public Node(string name) : this(name, []) { }
}

We model a directory tree with a record and print it, count its files, and compute its depth.

foreach (var child in node.Children)
{
Print(child, level + 1);
}

The Print method prints a node and then calls itself for each child with a deeper indentation level. A node without children is the base case: the loop simply does not run.

static int CountFiles(Node node) =>
node.Children.Count == 0 ? 1 : node.Children.Sum(CountFiles);

A leaf counts as one file; for other nodes, we sum the counts of the children. The method group CountFiles is passed directly to LINQ's Sum. The Depth method works the same way with Max.

$ dotnet run
src
  Program.cs
  Models
    User.cs
    Order.cs
  Services
    Mail
      SmtpSender.cs
    Billing.cs
files: 5, depth: 4

Backtracking

Backtracking explores all candidate solutions by making a choice, recursing, and then trying the next choice. It is used to generate permutations and combinations and to solve puzzles and constraint problems.

Program.cs
var result = new List<string>();
Permute("", "abc", result);

Console.WriteLine(string.Join(' ', result));
Console.WriteLine($"{result.Count} permutations");

int[] coins = [1, 2, 5];
Console.WriteLine($"ways to pay 10: {Ways(10, coins, 0)}");

static void Permute(string prefix, string rest, List<string> acc)
{
    if (rest.Length == 0)
    {
        acc.Add(prefix);
        return;
    }

    for (int i = 0; i < rest.Length; i++)
    {
        Permute(prefix + rest[i], rest.Remove(i, 1), acc);
    }
}

static int Ways(int amount, int[] coins, int start)
{
    if (amount == 0)
    {
        return 1;
    }

    int count = 0;

    for (int i = start; i < coins.Length; i++)
    {
        if (coins[i] <= amount)
        {
            count += Ways(amount - coins[i], coins, i);
        }
    }

    return count;
}

We generate all permutations of a string and count the ways to pay an amount with coins.

for (int i = 0; i < rest.Length; i++)
{
Permute(prefix + rest[i], rest.Remove(i, 1), acc);
}

At each level, every remaining character takes its turn as the next character of the prefix. When no characters remain, the prefix is a complete permutation. A string of n distinct characters has n! permutations.

for (int i = start; i < coins.Length; i++)
{
if (coins[i] <= amount)
{
count += Ways(amount - coins[i], coins, i);
}
}

The start parameter makes the method consider coins only in non-decreasing order, so that 1 + 2 and 2 + 1 are counted as the same combination. There are ten ways to pay 10 with coins of 1, 2, and 5.

$ dotnet run
abc acb bac bca cab cba
6 permutations
ways to pay 10: 10

Divide and conquer

Divide and conquer algorithms split a problem into parts, solve the parts recursively, and combine the results. Halving the problem at each step keeps the recursion depth small.

Program.cs
int[] data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

Console.WriteLine(BinarySearch(data, 23, 0, data.Length - 1));
Console.WriteLine(BinarySearch(data, 4, 0, data.Length - 1));
Console.WriteLine(Gcd(1071, 462));
Console.WriteLine(Power(2, 30));

static int BinarySearch(int[] arr, int target, int lo, int hi)
{
    if (lo > hi)
    {
        return -1;
    }

    int mid = lo + (hi - lo) / 2;

    return arr[mid].CompareTo(target) switch
    {
        0 => mid,
        > 0 => BinarySearch(arr, target, lo, mid - 1),
        _ => BinarySearch(arr, target, mid + 1, hi)
    };
}

static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b);

static long Power(long x, int n)
{
    if (n == 0)
    {
        return 1;
    }

    long half = Power(x, n / 2);

    return n % 2 == 0 ? half * half : half * half * x;
}

We implement binary search, the Euclidean algorithm for the greatest common divisor, and fast exponentiation.

return arr[mid].CompareTo(target) switch
{
0 => mid,
> 0 => BinarySearch(arr, target, lo, mid - 1),
_ => BinarySearch(arr, target, mid + 1, hi)
};

Binary search compares the middle element of a sorted array with the target and continues in the left or right half. The search for 4 ends in the base case lo > hi and returns -1.

long half = Power(x, n / 2);

Fast exponentiation computes xn from xn/2, so 230 needs only six calls (for n = 30, 15, 7, 3, 1, and 0) instead of 30 multiplications.

$ dotnet run
5
-1
21
1073741824

Stack overflow

Every recursive call consumes stack space, and the stack is limited, by on Linux the main thread gets the size set by ulimit -s, typically 8 MB, and on Windows it is 1 MB by default. When the recursion is too deep, the runtime terminates the process. A StackOverflowException cannot be caught.

Program.cs
Console.WriteLine(SumLoop(1_000_000));
Console.WriteLine(Sum(1_000_000));

static long Sum(int n) => n == 0 ? 0 : n + Sum(n - 1);

static long SumLoop(int n)
{
    long total = 0;

    for (int i = 1; i <= n; i++)
    {
        total += i;
    }

    return total;
}

We sum the numbers from 1 to one million with a loop and with recursion.

static long Sum(int n) => n == 0 ? 0 : n + Sum(n - 1);

The recursive version needs a million nested calls. The C# compiler does not perform tail call optimization, so every call keeps its frame on the stack. The process crashes after about 174,000 calls; the exact number depends on the platform and the build configuration. The loop prints the correct result before the crash, and exit code 134 indicates that the process was aborted.

$ dotnet run
500000500000
Stack overflow.
Repeated 174290 times:
--------------------------------
   at Program.<<Main>$>g__Sum|0_0(Int32)
--------------------------------
   at Program.<Main>$(System.String[])
$ echo $?
134

Replacing recursion with a stack

Any recursive algorithm can be rewritten with an explicit Stack<T>. The stack then lives on the heap and is limited only by available memory. This is the standard fix for recursion over deep or untrusted data.

Program.cs
var root = new Node("src",
[
    new("Program.cs"),
    new("Models", [new("User.cs"), new("Order.cs")]),
    new("Services", [new("Mail", [new("SmtpSender.cs")]), new("Billing.cs")]),
]);

var stack = new Stack<(Node Node, int Level)>();
stack.Push((root, 0));

while (stack.Count > 0)
{
    var (node, level) = stack.Pop();
    Console.WriteLine($"{new string(' ', level * 2)}{node.Name}");

    for (int i = node.Children.Count - 1; i >= 0; i--)
    {
        stack.Push((node.Children[i], level + 1));
    }
}

record Node(string Name, List<Node> Children)
{
    public Node(string name) : this(name, []) { }
}

We print the same directory tree as before without recursion.

while (stack.Count > 0)
{
var (node, level) = stack.Pop();

The stack holds the nodes that still have to be visited, together with their levels. Each iteration takes one node off the stack and prints it.

for (int i = node.Children.Count - 1; i >= 0; i--)
{
stack.Push((node.Children[i], level + 1));
}

The children are pushed in reverse order, so that the first child is popped first. The output is the same as in the recursive version.

$ dotnet run
src
  Program.cs
  Models
    User.cs
    Order.cs
  Services
    Mail
      SmtpSender.cs
    Billing.cs

Source

Local functions

StackOverflowException class

In this article we have written recursive methods in C#. See also the method, local functions, Stack, and merge sort tutorials.

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all C# tutorials.