Recursion in C# is a programming technique where a method calls itself to solve a problem. A recursive method breaks a larger problem into smaller versions of the same problem until it reaches a simple case that can be solved directly.
Recursion is useful for problems that naturally have repeated structure, such as factorial calculation, tree traversal, directory scanning, nested comments, graph exploration, and divide-and-conquer algorithms. It can make some solutions elegant, but it must be written carefully to avoid infinite calls and stack overflow errors.
What Is Recursion in C#?
Recursion happens when a method calls itself directly or indirectly. A recursive method usually has two important parts: a base case and a recursive case. The base case stops recursion. The recursive case moves the problem closer to the base case.
void CountDown(int number)
{
if (number == 0)
{
return;
}
Console.WriteLine(number);
CountDown(number - 1);
}
CountDown(5);This method prints numbers from 5 down to 1. Each call reduces the value by one. When the value becomes 0, the method returns and recursion stops.
Base Case in Recursion
The base case is the condition that stops the recursive calls. Without a base case, or with a base case that is never reached, the method keeps calling itself until the program crashes with a stack overflow.
int Factorial(int number)
{
if (number == 0)
{
return 1;
}
return number * Factorial(number - 1);
}Here, number == 0 is the base case. The recursive call reduces number, so the method eventually reaches the base case.
Recursive Case in Recursion
The recursive case is the part where the method calls itself with a smaller or simpler input. The recursive case must move toward the base case. If the input does not change correctly, recursion will not stop.
int Sum(int number)
{
if (number == 0)
{
return 0;
}
return number + Sum(number - 1);
}This method calculates the sum from number down to 1. The problem gets smaller with every call.
How Recursion Uses the Call Stack
Every method call in C# uses the call stack. When a recursive method calls itself, each call gets its own stack frame with its own local variables and return point. When the base case is reached, the calls start returning one by one.
This is why recursion can be memory-heavy. A deep recursive chain creates many stack frames. If the chain becomes too deep, the program can throw a StackOverflowException. This is not easy to recover from, so recursive depth should be controlled.
Factorial Using Recursion
Factorial is a classic recursion example because n! is defined in terms of (n - 1)!.
int Factorial(int number)
{
if (number < 0)
{
throw new ArgumentException("Number cannot be negative");
}
if (number == 0 || number == 1)
{
return 1;
}
return number * Factorial(number - 1);
}This method handles invalid input, stops at 0 or 1, and otherwise calls itself with a smaller number.
Recursion vs Iteration
| Feature | Recursion | Iteration |
|---|---|---|
| Technique | Method calls itself | Loop repeats code |
| Best for | Trees, nested structures, divide-and-conquer | Counting, simple repeated steps |
| Memory | Uses call stack | Usually less stack usage |
| Risk | Stack overflow if too deep | Infinite loop if condition is wrong |
Use recursion when it matches the structure of the problem and makes the code clearer. Use iteration when a simple loop solves the problem more directly.
Recursive Directory Traversal
Directory traversal is a realistic recursion example because folders can contain folders, and those folders can contain more folders. The same logic applies at every level.
void PrintFiles(string folderPath)
{
foreach (string file in Directory.GetFiles(folderPath))
{
Console.WriteLine(file);
}
foreach (string folder in Directory.GetDirectories(folderPath))
{
PrintFiles(folder);
}
}The method prints files in the current folder, then calls itself for each subfolder. This works because each subfolder is the same kind of problem as the original folder.
Tracing Recursive Calls
To understand recursion, it helps to trace method calls manually. Each recursive call pauses the current method and starts a new call with a smaller input. After the base case returns, the paused calls finish in reverse order.
int Sum(int number)
{
if (number == 0)
{
return 0;
}
return number + Sum(number - 1);
}Calling Sum(3) becomes 3 + Sum(2), then 3 + 2 + Sum(1), then 3 + 2 + 1 + Sum(0). The base case returns 0, and the final result becomes 6.
Fibonacci Recursion Problem
Fibonacci is often used to teach recursion, but the naive recursive version is inefficient because it repeats the same calculations many times. This makes it a good example of both recursion and its risks.
int Fibonacci(int n)
{
if (n <= 1)
{
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}This code is simple, but it becomes slow for larger values because it recalculates many smaller Fibonacci values repeatedly. A loop or memoization is usually better for production code.
Memoization with Recursion
Memoization means storing results that were already calculated so the method does not repeat expensive work. It is useful when recursion solves overlapping subproblems, such as Fibonacci or dynamic programming tasks.
int Fibonacci(int n, Dictionary<int, int> cache)
{
if (n <= 1)
{
return n;
}
if (cache.TryGetValue(n, out int value))
{
return value;
}
value = Fibonacci(n - 1, cache) + Fibonacci(n - 2, cache);
cache[n] = value;
return value;
}This version stores previous results in a dictionary. It keeps the recursive structure but avoids much of the repeated work.
Recursion with Tree Structures
Tree structures are one of the best practical uses of recursion. A tree node can contain child nodes, and each child node can contain more child nodes. The same operation can be applied recursively to every node.
class Node
{
public string Name { get; set; } = "";
public List<Node> Children { get; set; } = new();
}
void PrintTree(Node node, int level = 0)
{
Console.WriteLine(new string(' ', level * 2) + node.Name);
foreach (Node child in node.Children)
{
PrintTree(child, level + 1);
}
}This method prints a node and then recursively prints each child. The level parameter controls indentation so the tree structure is visible.
Direct and Indirect Recursion
Direct recursion happens when a method calls itself. Indirect recursion happens when one method calls another method, and that second method eventually calls the first method again. Both forms need a safe stopping condition.
void A(int value)
{
if (value <= 0) return;
B(value - 1);
}
void B(int value)
{
if (value <= 0) return;
A(value - 1);
}Indirect recursion can be harder to debug because the recursive cycle is spread across more than one method. Keep it rare and well documented.
When to Avoid Recursion
Avoid recursion when the depth can grow very large or when a simple loop is more readable. For example, counting from 1 to 1000 is clearer with a loop. Recursion is not automatically better just because it looks elegant.
Also avoid recursion when input comes from users or external systems and depth is not controlled. A malicious or unusually large input could create deep recursive calls and crash the program.
Tail Recursion in C#
Tail recursion means the recursive call is the last operation in the method. Some languages optimize tail recursion to avoid growing the call stack. In C#, you should not rely on tail-call optimization for normal application code. The runtime may optimize some cases, but it is not a safe general design assumption.
If a recursive method can run very deep, prefer an iterative version or manage your own stack data structure. This gives predictable memory behavior and avoids stack overflow risk.
Recursive Search Example
Recursive search is common when data is nested. For example, a category can contain child categories. To find one category, the method can check the current node and then search its children.
Node? FindNode(Node node, string name)
{
if (node.Name == name)
{
return node;
}
foreach (Node child in node.Children)
{
Node? found = FindNode(child, name);
if (found != null)
{
return found;
}
}
return null;
}This method returns as soon as it finds a match. If no child contains the value, it returns null. This is a clean recursive pattern for nested structures.
Input Validation in Recursive Methods
Recursive methods should validate input before recursion starts. Invalid input can make the base case unreachable or create meaningless results. For example, factorial should reject negative numbers because the simple recursive formula does not support them.
When recursion is exposed through a public method, it is often useful to place validation in a public wrapper and keep the recursive worker method private. This keeps the recursive logic focused and protects it from bad input.
For maintainability, recursive code should make the base case, the smaller recursive step, and the return path easy to see. If those three parts are hidden, the method will be difficult to debug even if it works.
In production code, recursion should also be tested with the smallest input, a normal input, and a boundary input. For a factorial method, test 0, 1, 5, and invalid negative numbers. For a tree traversal method, test an empty tree, a single node, and a deeper tree. These tests quickly reveal whether the base case and recursive step are correct.
Recursive methods become much easier to maintain when the method name explains the task and each parameter has a clear role. Avoid passing many changing values unless they are required for the recursive state.
Common Mistakes with Recursion
- Forgetting the base case.
- Writing a recursive case that does not move toward the base case.
- Using recursion for simple loops where iteration is clearer.
- Ignoring stack depth and causing stack overflow.
- Repeating expensive calculations without caching or memoization.
Best Practices for Recursion in C#
Always define the base case first, make sure each recursive call moves toward that base case, validate input, and avoid recursion when a simple loop is easier. For large or unpredictable depth, consider an iterative solution with your own stack or queue.
Continue learning C# in order
Follow the topic sequence with the previous and next lesson.