Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 182 ยท Methods

Recursion

Learn recursion in C# - base cases, how the call stack grows, why StackOverflowException cannot be caught, memoization with Dictionary, and when a loop is better.

Some problems contain smaller copies of themselves. A folder contains folders, a sentence is a word plus a shorter sentence, and the number of ways to climb ten stairs is built from the number of ways to climb nine and eight. Recursion is the technique of solving such a problem with a method that calls itself on a smaller piece of the problem until the piece is so small that the answer is obvious.

Recursion feels strange at first because the method is used while it is still being defined. The trick is to stop worrying about the whole chain of calls and trust two things: a simple case you can answer directly, and a rule that turns a big case into a smaller one. This lesson shows how to write recursive methods, what the runtime does while they run, why too much recursion crashes a program in a way you cannot catch, how to speed up repeated work with memoization, and when a plain loop is the better tool.

The two parts of every recursive method

Every correct recursive method has:

  1. A base case: an input small enough to answer without calling the method again.
  2. A recursive case: a call to the same method with an input that is closer to the base case.

The classic example is the factorial. 5! means 5 * 4 * 3 * 2 * 1, and notice that 5! = 5 * 4!. So n! is n times the factorial of n - 1, and 0! is defined as 1.

C# Factorial with recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Follow Factorial(3) by hand. The call needs 3 * Factorial(2), but Factorial(2) is not known yet, so it must run first and needs 2 * Factorial(1). Factorial(1) hits the base case and returns 1. Now the waiting calls finish in reverse order: 2 * 1 = 2, then 3 * 2 = 6. Each call waits for the one it started.

To check a recursive method, ask two questions. Does every input eventually reach a base case? Does each recursive call get strictly closer to one? If both answers are yes, the method terminates.

What the call stack does

Each time a method is called, the runtime reserves a block of memory called a stack frame for that call's parameters, local variables and the place to return to. Frames are stacked on top of each other: the newest call is on top, and when it returns its frame is removed. This is the call stack.

Recursion simply puts many frames of the same method on the stack at once. We can watch it by printing the depth with indentation:

C# Watching the stack grow and shrink

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The output shows four "enter" lines going deeper and then four "leave" lines coming back out in the opposite order. That mirror image is the stack: last in, first out. Code placed before the recursive call runs on the way down; code placed after it runs on the way back up.

That ordering gives you a free way to reverse things. Printing after the recursive call reverses the order:

C# Reversing a string recursively

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

text[1..] is a range that takes everything after the first character. It copies the remaining characters into a new string, so this version creates many short-lived strings. That is fine for teaching; for real code use string.Create, Array.Reverse or a loop.

Recursion over nested data

Recursion shines when the data itself is nested to an unknown depth. A tree of folders is the usual example: you cannot write a fixed number of loops because you do not know how deep the tree goes.

C# Summing a folder tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Notice that the base case here is hidden: a folder with no children makes the foreach run zero times, so the method returns without recursing. Base cases do not always look like an if.

Stack depth and StackOverflowException

The call stack is small. On .NET, the main thread of a typical 64-bit program gets roughly 8 MB on Linux and 1 MB on Windows by default, which allows somewhere between ten thousand and a few hundred thousand frames depending on how large each frame is. If recursion goes deeper than that, the runtime throws away the program.

A stack overflow in .NET cannot be caught. Unlike most errors, StackOverflowException does not travel up to a catch block: the process is terminated immediately. A try/catch around runaway recursion will not save you. You must prevent it.

The cause is nearly always a missing or unreachable base case:

C#
// Do not run this: it never stops.
static int Broken(int n)
{
    return n * Broken(n - 1);   // no base case: n goes 3, 2, 1, 0, -1, -2 ...
}

Calling Broken(3) would pile up frames until the process dies with Stack overflow. and a repeating stack trace. We do not run it here because the sandbox would simply abort the program, but you can reproduce it safely in a console project on your own machine.

Even with a correct base case, a huge input can exhaust the stack. A recursive sum from 1 to 1,000,000 has a perfect base case and still crashes. Two ways out:

  • Write a loop (shown below), which uses one frame no matter how large n is.
  • Add a depth limit and fail with a clear exception you control. The next example does this:
C# Guarding against excessive depth

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The guard throws an ordinary exception, which can be caught, long before the stack is really exhausted. The exact safe limit depends on the platform, so pick a conservative number or switch to iteration when inputs can be large.

Fibonacci and the cost of repeated work

The Fibonacci numbers start 0, 1, 1, 2, 3, 5, 8, ..., and each one is the sum of the two before it. The definition maps directly to code:

C# Naive Fibonacci counts its own calls

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The counter shows the problem: Fib(25) needs a quarter of a million calls to produce a number below 100,000. Fib(5) calls Fib(3) twice and Fib(2) three times, and it only gets worse as n grows: the number of calls roughly multiplies by 1.6 for every step. The method solves the same small subproblems again and again.

Memoization: remember answers

Memoization stores the result of each call in a dictionary the first time it is computed. Later calls with the same argument read the stored value instead of recomputing it.

C# Fibonacci with a Dictionary cache

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

With the cache, Fib(25) makes only a few dozen calls and Fib(90) is instant. Each value is computed exactly once, so the cost drops from exponential to linear. Combining recursion with stored answers is the core idea of dynamic programming.

Two cautions: the cache must live outside the method (here, a variable captured by a local function), and it only works for pure methods whose result depends solely on their arguments.

Iteration versus recursion

Anything recursive can be written with a loop and, if needed, your own Stack<T>. A loop uses one stack frame and cannot overflow from depth. For simple linear problems the loop is also clearer and faster:

C# The same Fibonacci with a loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The line (previous, current) = (current, previous + current) swaps and adds in one step using a tuple deconstruction.

Prefer recursion when the data is naturally a tree or graph (folders, JSON, expression trees), or the problem divides into independent halves (merge sort, binary search, quicksort). Prefer a loop when the recursion is just counting or accumulating, the depth can be large, or performance in a hot path matters.

C# does not guarantee tail-call optimization, the trick in some languages where return Helper(n - 1, acc) reuses the current frame. The JIT sometimes does it, but you can never rely on it, so do not assume a tail-recursive method is safe for deep inputs.

Mutual recursion

Two methods can call each other. Each call moves closer to a base case in one of them:

C# Even and odd by mutual recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

This is a toy (use n % 2 == 0 in real code), but mutual recursion is genuinely useful in parsers, where "expression" calls "term", which calls "factor", which calls "expression" again for parenthesized parts.

Common mistakes

  • No base case, or one that is never reached (for example, a base case n == 0 when n can start negative). Use <= where it is safe.
  • Not making progress: calling F(n) from inside F(n).
  • Recomputing overlapping subproblems without a cache.
  • Catching StackOverflowException: it cannot be done; limit depth instead.
  • Forgetting the long or BigInteger: Factorial(21) overflows long. See integer types.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the two essential parts of a correct recursive method?

    The base case ends the recursion, and the recursive case must make the input smaller so that it eventually reaches the base case.
  2. 2. What happens when recursion goes too deep in a .NET program?

    A stack overflow ends the process immediately. Prevent it with a correct base case, a depth limit or iteration.
  3. 3. Why is the naive recursive Fibonacci so slow for larger inputs?

    Fib(n - 1) and Fib(n - 2) share almost all of their subproblems, so the number of calls grows exponentially. Memoization computes each value once.
  4. 4. Which statement about memoization is true?

    Memoization is only safe for pure methods. The cache turns repeated computation into a lookup, but you still need a base case.
  5. 5. In a method, code placed after the recursive call runs when?

    The deeper call must return first, so code after it runs while the stack unwinds, in reverse order of the calls.

Summary

  • A recursive method calls itself with a smaller input and needs a base case that stops the chain.
  • Each call adds a stack frame; code before the call runs on the way down, code after it on the way back up.
  • A stack overflow cannot be caught in .NET. Prevent it with correct base cases, depth guards, or loops.
  • Naive recursion that repeats subproblems (Fibonacci) can be fixed with memoization using a Dictionary.
  • Prefer recursion for trees and divide-and-conquer; prefer loops for simple counting and very deep inputs.
  • C# gives no tail-call guarantee, and mutual recursion is useful in parsers.

Next: Lambda Expressions