Recursion is when a method calls itself to solve a smaller version of the same problem. It shows up naturally any time the data you're working with has a nested shape: a cart bundle that contains other bundles, a category tree, a folder that contains folders, a comment with replies. This chapter explains how recursive methods work, what makes them safe (or unsafe), how they use the call stack, and when a plain loop is the better choice.

A recursive method follows the same pattern every time. It does a tiny piece of the work itself, then asks itself to do the rest on a slightly smaller input. Eventually the input gets so small that there's nothing left to do, and the method returns directly without calling itself. That stopping point is the base case. Every step that's not the base case is the recursive case.

Think of it like opening a stack of nested gift boxes. You open the outer box. Inside is either a gift (base case: hand it over and stop), or another box (recursive case: open that one the same way). The procedure is identical at every level, and it only stops when there are no more boxes to open.

A recursive method needs both pieces:

If either piece is missing or wrong, the method either returns the wrong answer or runs until the program crashes with a StackOverflowException. We'll look at that crash in detail later.

Factorial is the textbook example, and it's worth walking through once because it makes the structure obvious before we move to e-commerce examples that have more moving parts. The factorial of n (written n!) is the product of every integer from 1 up to n. So 4! = 4 * 3 * 2 * 1 = 24.

You can describe factorial in two lines:

That description maps directly to code:

Notice how the method calls itself with n - 1 each time. The input gets smaller on every call, so it eventually hits n == 0 and stops. That's the whole pattern.

Walking Through Factorial(4)

Reading recursive code top to bottom doesn't tell you what's happening at runtime. The clearer view is to trace the calls one at a time, watching them stack up and then unwind.

Factorial(4) starts running. 4 != 0, so it returns 4 * Factorial(3). But Factorial(3) hasn't returned yet, so the runtime pauses Factorial(4) and starts Factorial(3). The same thing happens at each level until we hit the base case.

Each box is a paused method waiting on the next one to finish. Once Factorial(0) returns 1, the chain unwinds in reverse:

Five calls in total for Factorial(4): one for each value from 4 down to 0. The work happens twice. Going down, each call sets up a multiplication that's waiting for a result. Coming back up, each call performs that multiplication with the value it just got back.

Factorial is neat, but the reason recursion matters in real code is that some data has a naturally nested shape. A shopping cart with bundles is a clean example.

A regular product has a price. A bundle is a collection of items, where each item is either a product or another bundle. So a "Home Theater Bundle" might contain a TV, a soundbar, and a "Cable Pack Bundle" that itself contains an HDMI cable and an optical cable. To compute the total price of the top-level bundle, you have to walk through every item, adding product prices directly and recursing into sub-bundles to add up their contents.

You can't write this cleanly with a single loop. The depth of nesting isn't known ahead of time. Some bundles are flat, some are nested two levels deep, some five. Recursion handles all of these with one method.

Here's the data model and the recursive total:

Read the Total method carefully. It has the same two parts as Factorial: a base case (the item is a plain Product, return its price) and a recursive case (the item is a Bundle, sum the totals of its children). The foreach loop walks the bundle's direct children, but the recursive Total(child) call is what handles the nested structure. If a child is itself a bundle, that call will loop through its children, and so on down to the leaf products.

The trace for the home theater bundle looks like this:

Notice that the structure of the calls mirrors the structure of the data. Recursion is the natural shape for problems where the data has a recursive shape.

A second e-commerce example with a tree shape: counting how many categories exist in a category tree. An online store typically organizes products under categories like "Electronics", which has subcategories like "Audio", which has subcategories like "Headphones". Each category can have any number of subcategories, including none.

The base case is implicit here. When a category has no subcategories, the foreach loop doesn't execute, and the method returns 1 for just that category. There's no separate if check, because the loop itself handles the empty case correctly.

The recursive case adds 1 for the current category, then adds the count from each subtree. Each recursive call returns the size of one subtree, which gets folded into the running total.

Look at the call shape. From "Electronics", the method recurses into "Audio" and "Computers". From "Audio", it recurses into "Headphones" and "Speakers", which return 1 each. From "Computers", it recurses into three children, one of which ("Accessories") has its own children. The recursive calls form a tree that exactly mirrors the data tree.

Every time a method is called, the runtime creates a stack frame for it. The frame holds the method's local variables, its parameters, and the spot in the calling code to return to when the method finishes. Stack frames pile up on top of each other in a region of memory called the call stack, with the most recent call on top.

When a method returns, its frame is removed from the top of the stack, and execution resumes in the caller's frame. With normal (non-recursive) code, you rarely think about stack frames because they're created and destroyed quickly. With recursion, the stack visibly grows: each recursive call adds a frame before any of them return.

Picture the call stack during Factorial(4) at the moment Factorial(0) is about to return. All five frames exist at once:

The frame at the top, Factorial(0), is the active one. It's about to return 1. When it does, its frame is removed, and Factorial(1) becomes active. It computes 1 * 1, returns 1, its frame is removed, and Factorial(2) becomes active. And so on, until only Main is left and the program continues.

The same shape applies to the cart bundle example, except the calls form a tree rather than a single chain (since a bundle can have multiple children, each of which spawns its own subtree of calls). At any given moment, the stack contains the path from the root to whichever leaf is currently being processed.

Two things to internalize:

The call stack has a fixed size. On Windows, the default is roughly 1 MB per thread, which works out to a few thousand stack frames depending on how much data each frame holds. On Linux, it's typically 8 MB. The exact number varies with the runtime, the frame size, and the OS, but it's always bounded.

When recursion goes too deep, the runtime runs out of stack space and throws StackOverflowException. The catch: this exception is special. You cannot catch it with a regular `try`/`catch` in most cases. The runtime treats it as fatal because the stack is in an unrecoverable state, and the process usually terminates. You see the crash, and that's it.

Two ways to trip this:

Missing base case. The method calls itself forever because the input never reaches the stopping condition.

Recursing on the wrong "smaller" input. The method has a base case, but the recursive call doesn't move toward it.

The second mistake is easier to make and harder to spot, because the code looks structurally right. The fix is to read the recursive call carefully and confirm that whatever you're passing is genuinely closer to the base case.

Both bugs surface as a crash. Visual Studio and dotnet run print something like:

The "Repeat 16382 times" line is the giveaway: the same method is on the stack thousands of times. That's almost always a missing or wrong base case.

A lot of recursive algorithms can be rewritten as loops. Sometimes the loop is clearer, sometimes the recursion is. Sometimes the recursion is correct but unsafe for large inputs, and the loop is the only practical choice.

A simple comparison: summing a list of prices. The recursive version walks one item at a time, asking itself to sum the rest:

The iterative version does the same work with a loop:

Both produce the same result. The iterative version is shorter, doesn't grow the stack with input size, and is what every C# developer would actually write for this problem. The recursive version is fine for teaching the structure, but it would crash on a list of a million prices.

Here's the trade-off side by side:

The honest summary: use iteration for flat data, especially when input size could be large. Use recursion for naturally nested data (trees, bundles, parsed expressions) where the recursive structure mirrors the data. If a recursive algorithm could hit a deep input, rewrite it iteratively with an explicit Stack<T> or Queue<T>, which moves the frame storage from the call stack onto the heap.

For the cart bundle example, the iterative version would look like this:

It works, and it can handle bundles nested arbitrarily deep without ever risking a stack overflow. But you'll notice it's longer and harder to follow than the recursive version. That's the trade-off in a nutshell.

You might have heard that "tail-recursive" methods don't add to the stack. A tail call is when the recursive call is the very last thing the method does (nothing happens to the result, it's just returned directly). In languages like F#, Scheme, or Haskell, the compiler is required to optimize tail calls into loops, so a tail-recursive method runs in constant stack space.

C# does not guarantee this. The C# language specification doesn't require tail-call optimization. The 64-bit RyuJIT (the default JIT compiler in modern .NET) does perform tail-call optimization in some cases, but it's not something you can rely on. The same method might be optimized on one runtime and not on another, or might be optimized in a release build but not a debug build.

So in C#, the practical advice is: don't write recursive code assuming the runtime will turn it into a loop. If you need a loop, write a loop. If recursion is the right shape for the problem and the input depth is bounded, write the recursion. Don't lean on tail-call optimization as a safety net.

For comparison, here's what a tail-recursive factorial looks like:

The recursive call here is the last expression in the method. In a language with guaranteed tail-call optimization, this would run in constant stack space. In C#, it might or might not. Treat it as a curiosity, not a safety mechanism.

A short tour of the failures that catch people when they're writing recursive methods.

Missing or Wrong Base Case

The most common bug. Either there's no if to stop the recursion at all, or the condition can never be true given the inputs. Both lead to StackOverflowException.

What's wrong with this code?

The base case checks for n == 5, but the method is called with 3 and decrements from there. n will be 3, 2, 1, 0, -1, -2, ... and never reach 5. The recursion never stops.

Fix:

Whenever you write a base case, ask: "Given the inputs this method will see, will the recursion definitely reach this condition?" If the answer isn't a clear yes, rewrite it.

Recursing on the Wrong "Smaller" Input

The base case is right, but the recursive call doesn't move toward it. The classic version is forgetting to subtract:

n never changes between calls, so the recursion runs forever. The fix is to pass n - 1. Always read the recursive call out loud: "I'm asking this method to solve the same problem on a strictly smaller input." If that's not literally true, the call is broken.

Deep Recursion on Potentially Large Input

A recursive method that works fine on hand-typed test data can blow up on real-world data. Summing a list of 10 prices recursively works. Summing a list of a million prices recursively crashes.

The fix is to recognize when input size is unbounded (or could grow) and use iteration in those cases. Recursion is appropriate when the depth of recursion is bounded by the structure of the data (a tree of bundles isn't going to be a million levels deep), not bounded by the number of items in a flat collection.

Doing the Same Work Twice (Without Realizing)

Some recursive solutions accidentally recompute the same subproblem many times. The naive recursive Fibonacci is the famous example:

Fib(5) calls Fib(4) and Fib(3). But Fib(4) also calls Fib(3). And both of those call Fib(2) separately. By Fib(30), the same subproblems are recomputed millions of times. The method works, but it's catastrophically slow.

This is more of a complexity issue than a recursion issue (the fix is to memoize results or convert to iteration), but it's worth knowing the shape so you spot it.