C# Recursion
Recursion is when a method calls itself to solve a smaller version of the same problem. Every recursive method needs a base case — a condition that stops the recursion — to avoid infinite calls.
Recursion is often used for problems that have a naturally recursive structure, like calculating factorials, traversing trees, or computing Fibonacci numbers.
static int Method(int n) {
if (n == baseCase) return baseValue;
return Method(n - 1);
}Base case and recursive case
The base case is the simplest scenario that returns a result directly without further recursion. The recursive case breaks the problem down and calls the method again with a smaller input.
Stack considerations
Each recursive call adds a new frame to the call stack. Too many recursive calls without reaching a base case causes a StackOverflowException.
using System;
class Program {
static int Factorial(int n) {
if (n == 0) return 1;
return n * Factorial(n - 1);
}
static void Main() {
Console.WriteLine(Factorial(5));
}
}120Factorial(5) calls Factorial(4), Factorial(3), and so on until the base case n == 0 is reached.
using System;
class Program {
static int Fibonacci(int n) {
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
static void Main() {
Console.WriteLine(Fibonacci(6));
}
}8Fibonacci(6) recursively sums the two preceding Fibonacci numbers until reaching the base case.
Key points
- Recursion is when a method calls itself.
- Every recursive method needs a base case to stop the recursion.
- Recursion can be a clean way to solve naturally recursive problems.
- Excessive recursion depth can cause a StackOverflowException.