C# Recursion
Recursion means a method solves a problem by calling itself with a smaller or simpler version of the same problem. It matters because many tasks, especially tree-shaped data, nested structures, and divide-and-conquer algorithms, are easier to express recursively than with repeated loops.
A recursive method must have a stopping point. Without a clear base case, the method keeps calling itself until the program runs out of stack space.
Overview: How C# Recursion Works
In C#, recursion is not a special kind of method declaration. A recursive method is an ordinary method whose body contains a call to itself, directly or indirectly. The compiler allows this because method calls are resolved by name and signature; a method may refer to itself just as it may refer to another method in the same class.
The key idea is to split the work into two parts: a base case and a recursive case. The base case handles the smallest answer immediately, such as 0! being 1, an empty folder having no files, or an empty list having a sum of 0. The recursive case does a small amount of current work, then asks the same method to solve the rest.
At runtime, every method call gets its own stack frame. A stack frame stores that call’s parameters, local variables, and return location. If Factorial(4) calls Factorial(3), those are two separate active calls with separate number parameter values. The earlier call waits while the later call runs. When the deepest base case returns, the waiting calls resume in reverse order and combine their results.
This call stack is why recursion is powerful and why it has limits. Each call consumes stack memory. A recursion depth of 10 is harmless; a depth of a million will usually fail with a StackOverflowException. In .NET, stack overflows are severe and normally terminate the process, so recursive methods must be designed so they get closer to a base case on every path.
Recursion is most natural when the data or problem is recursive: a folder contains files and folders, a tree node contains child nodes, an expression contains subexpressions, and a search range can be split into smaller ranges. For simple counting, a for or while loop is usually clearer and avoids stack growth.
Syntax
static returnType MethodName(parameters)
{
if (baseCaseCondition)
{
return baseCaseValue;
}
return combinationOfCurrentWorkAndMethodName(smallerProblem);
}| Part | Meaning |
|---|---|
baseCaseCondition |
The condition that stops recursion. It must be reachable. |
baseCaseValue |
The direct answer for the smallest problem. |
smallerProblem |
Arguments that move closer to the base case, such as number - 1 or index + 1. |
combinationOfCurrentWork |
How this call combines its own work with the result returned by the smaller call. |
The recursive call can appear in a return expression, inside an if, inside a loop, or as part of a larger algorithm. What matters is that each recursive path eventually stops.
Examples
Factorial: Returning Through the Call Stack
using System;
class Program
{
static void Main()
{
Console.WriteLine(Factorial(5));
Console.WriteLine(Factorial(0));
}
static int Factorial(int number)
{
if (number < 0)
{
throw new ArgumentOutOfRangeException(nameof(number), "Factorial is not defined for negative integers.");
}
if (number == 0 || number == 1)
{
return 1;
}
return number * Factorial(number - 1);
}
}Output:
120
1Factorial(5) returns 5 * Factorial(4). That call waits for Factorial(4), which waits for Factorial(3), and so on until Factorial(1) returns 1. Then the pending multiplications finish in reverse order: 2 * 1, 3 * 2, 4 * 6, and 5 * 24.
Summing an Array Recursively
using System;
class Program
{
static void Main()
{
int[] scores = { 8, 12, 7, 5 };
Console.WriteLine(SumFrom(scores, 0));
}
static int SumFrom(int[] numbers, int index)
{
if (index == numbers.Length)
{
return 0;
}
return numbers[index] + SumFrom(numbers, index + 1);
}
}Output:
32This method treats the sum as the first remaining number plus the sum of everything after it. The base case is an index equal to the array length, meaning there are no numbers left. In production code, a loop or LINQ’s Sum would usually be simpler for arrays, but this example makes the shrinking problem visible.
Walking a Tree of Categories
using System;
using System.Collections.Generic;
class Category
{
public string Name { get; }
public List<Category> Children { get; } = new List<Category>();
public Category(string name)
{
Name = name;
}
}
class Program
{
static void Main()
{
Category courses = new Category("Courses");
Category cs = new Category("C#");
cs.Children.Add(new Category("Methods"));
cs.Children.Add(new Category("Classes"));
courses.Children.Add(cs);
courses.Children.Add(new Category("SQL"));
PrintCategory(courses, 0);
}
static void PrintCategory(Category category, int depth)
{
Console.WriteLine(new string(' ', depth * 2) + category.Name);
foreach (Category child in category.Children)
{
PrintCategory(child, depth + 1);
}
}
}Output:
Courses
C#
Methods
Classes
SQLThis is the kind of problem where recursion fits naturally. Each Category can contain more Category objects, so PrintCategory prints one node and then uses the same method for each child node. The depth parameter is extra state carried through the recursion so the output can be indented.
Binary Search with Divide and Conquer
using System;
class Program
{
static void Main()
{
int[] numbers = { 2, 4, 7, 9, 12, 18, 21 };
Console.WriteLine(BinarySearch(numbers, 12, 0, numbers.Length - 1));
Console.WriteLine(BinarySearch(numbers, 5, 0, numbers.Length - 1));
}
static int BinarySearch(int[] numbers, int target, int left, int right)
{
if (left > right)
{
return -1;
}
int middle = left + (right - left) / 2;
if (numbers[middle] == target)
{
return middle;
}
if (target < numbers[middle])
{
return BinarySearch(numbers, target, left, middle - 1);
}
return BinarySearch(numbers, target, middle + 1, right);
}
}Output:
4
-1Binary search works only on sorted data. Each recursive call discards half of the remaining range, so the maximum depth grows slowly compared with a method that removes only one item at a time.
How Recursion Works Step by Step
- The caller invokes the recursive method with the original problem.
- The method checks its base case before making another call.
- If the base case is not true, the method creates a smaller problem and calls itself.
- The CLR places a new stack frame on the call stack for the new call. Earlier calls remain paused.
- Eventually a call reaches the base case and returns a direct answer.
- Each paused call resumes, receives the returned value, combines it with its own work, and returns to its caller.
- When the first call returns, recursion is complete and the caller receives the final result.
C# and the CLR do not guarantee tail-call optimization for normal C# recursion. Even when a recursive call is the final action in a method, you should not rely on the runtime turning it into a loop. If the depth can be large, write an explicit loop or use an explicit data structure such as Stack<T>.
Common Mistakes
Forgetting the Base Case
static int CountDown(int number)
{
return CountDown(number - 1);
}This method never stops. It makes smaller numbers forever and eventually overflows the call stack. A corrected version returns when the number reaches zero:
using System;
class Program
{
static void Main()
{
CountDown(3);
}
static void CountDown(int number)
{
if (number == 0)
{
Console.WriteLine("Done");
return;
}
Console.WriteLine(number);
CountDown(number - 1);
}
}Output:
3
2
1
DoneMoving Away from the Base Case
static int SumTo(int number)
{
if (number == 0)
{
return 0;
}
return number + SumTo(number + 1);
}The base case exists, but positive inputs move upward instead of downward, so SumTo(3) never reaches 0. The recursive argument must move toward the base case:
using System;
class Program
{
static void Main()
{
Console.WriteLine(SumTo(3));
}
static int SumTo(int number)
{
if (number < 0)
{
throw new ArgumentOutOfRangeException(nameof(number));
}
if (number == 0)
{
return 0;
}
return number + SumTo(number - 1);
}
}Output:
6Using Recursion for Very Deep Linear Work
static int CountItems(int count)
{
if (count == 0)
{
return 0;
}
return 1 + CountItems(count - 1);
}This compiles, but it is a poor design when count can be very large because it needs one stack frame per item. A loop uses constant stack space and is better for simple linear counting.
Best Practices
- Write the base case first, and make it obvious.
- Ensure every recursive path moves closer to a base case.
- Validate inputs that would make the recursion meaningless, such as negative values for factorial.
- Use recursion for naturally recursive data such as trees, nested menus, folders, and divide-and-conquer algorithms.
- Prefer loops for simple linear repetition over large collections.
- Keep recursive methods small. Extra unrelated work makes it harder to see whether the recursion stops correctly.
- Be careful with shared mutable state. Passing state as parameters is often easier to reason about.
- Do not rely on tail-call optimization in C# for stack safety.
Practice Exercises
- Write a recursive method named
Powerthat accepts a base number and a non-negative exponent. For example,Power(2, 4)should return16. - Write a recursive method that counts how many times a target string appears in a
string[]. - Create a simple
Folderclass with child folders and write a recursive method that counts all folders in the tree, including the root.
Summary
- Recursion is a method calling itself to solve a smaller version of the same problem.
- Every recursive method needs a reachable base case.
- Each recursive call gets its own stack frame with separate parameters and locals.
- Results return from the deepest call back toward the original caller.
- Recursion is excellent for trees, nested structures, and divide-and-conquer problems.
- Loops are usually better for very deep or simple linear repetition because recursion grows the call stack.
