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.
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.
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.
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.
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.
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.
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.
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.
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
In this article we have written recursive methods in C#. See also the method, local functions, Stack, and merge sort tutorials.
Author
List all C# tutorials.