Recursion is when a function calls itself to solve a smaller version of the same problem. It applies any time data has nested structure: a category that contains subcategories, a folder that contains subfolders, a discount tier that builds on the previous tier. This lesson covers what recursion is, the two parts every recursive function needs, how the call stack supports it, when to pick recursion over a regular loop, and the common bugs.

A recursive function is a function that, somewhere in its body, calls itself with a different argument. That self-call is the only thing that makes it "recursive." Everything else, the parameter list, the return type, the way it is invoked from the outside, is identical to any other function.

A small example to show the shape. An online store gives a loyalty greeting that repeats the customer's name a few times to fit a banner. Written with recursion:

Read the function from top to bottom. If times has reached 0, it returns and does nothing. Otherwise, it prints one line and then calls itself with times - 1. Each call hands off a smaller problem to the next call. Eventually the count reaches 0 and the chain unwinds.

greet could be written with a for loop, and for this problem the loop is the simpler choice. The example shows the shape: a function that calls itself with a smaller input until some stopping condition is reached.

Every recursive function has two pieces. The base case is the version of the problem so small or simple that it can be answered directly, with no further recursion. The recursive case is everything else: it breaks the problem into a smaller one, calls itself on that smaller piece, and combines the result.

Without a base case, the function calls itself forever (or until the program crashes, covered shortly). Without a recursive case, the function is not recursive at all.

A second example: compute the total of a list of cart prices by recursion instead of a loop.

The base case is index == prices.size(). When the index has walked past the last element, there is nothing left to add, so the function returns 0.0. The recursive case takes the price at the current index and adds it to whatever the rest of the cart totals to. That "rest of the cart" is the smaller problem.

Walk through the call sequence for the input {19.99, 4.49, 12.00, 7.50}:

Then the chain unwinds: 7.50 + 0.0 = 7.50, 12.00 + 7.50 = 19.50, 4.49 + 19.50 = 23.99, 19.99 + 23.99 = 43.98. The final value bubbles back up to main.

A flat list of numbers is not a great motivator for recursion, because a for loop does the same job with less ceremony. The wins come later, when the data itself is nested. First, the mechanics.

To see why recursion works, consider where C++ stores function calls while they run. Every time a function is called, the program reserves a chunk of memory called a stack frame for that call. The frame holds the function's parameters, its local variables, and the return address (where to jump back to when the function returns).

Frames are stacked one on top of the other, in the order the calls happen. When a function returns, its frame is removed from the top of the stack, and execution continues in the caller's frame. This region of memory is the call stack, and it works like a stack of cafeteria trays: the last one pushed on is the first one removed.

Recursion does not need anything special. Each recursive call gets its own frame, with its own copy of the parameters and local variables. The frames do not interfere with each other, because the parameter index in cartTotal(prices, 2) lives in a different frame from the index in cartTotal(prices, 3).

The stack during the deepest point of the cartTotal example above. The most recent call is at the top:

Each frame is paused, waiting for the call it made to return. The frame at the top, cartTotal(prices, 4), has hit the base case and is about to return 0.0. That value flows back into the frame below, which can now finish its own addition and return. The stack shrinks one frame at a time until control reaches main.

The C++ standard does not say how big the call stack is, but it has a fixed size set by the operating system: typically 1 MB on Windows, 8 MB on Linux for the main thread. That is enough for thousands of nested calls but not millions. The behavior when this limit is exceeded is covered later.

Every recursive call adds one stack frame. A function with a depth of N uses N frames. A frame is small (tens of bytes), but a function with many local variables or large parameters can push that up. For deeply nested recursion, total stack usage matters.

The clearest way to read a recursive function is to walk through its calls on a small input by hand. The example: a tiered cumulative discount, the kind a store might apply when a customer hits multiple loyalty milestones.

The rule: starting from a base discount of 0.0, every loyalty tier adds 5% of the price plus whatever discount the previous tier produced. So tier 1 adds 5%, tier 2 adds 5% plus the previous discount, and so on. Each tier depends on the previous one, which fits recursion.

Trace it on price = 100.0. Each call computes previous + (price * 0.05) + previous * 0.10, which simplifies to 1.10 * previous + 5.0.

Each call sits on the stack waiting for the next call to come back with previous, and the result of each level depends on the level below. This is a recursive dependency, not a pattern that maps cleanly to a for loop without manually carrying state.

The next example shows where recursion pulls its weight. An online store has product categories like Electronics, Clothing, and Home. Each category can contain its own subcategories (Electronics has Phones, Laptops, Audio) and direct products. Subcategories can have their own subcategories. The structure is a tree, and trees are recursive by nature: a tree is a node plus a list of smaller trees.

To sum the prices of every product in a category, including everything in its subcategories, walk the tree. With a for loop alone, an explicit stack data structure is needed to remember which subcategories have not been visited yet. With recursion, the call stack does that bookkeeping automatically.

The function has the same two pieces as before. The base case is implicit: if a category has no subcategories, the second for loop does nothing and the function returns the sum of its direct products. The recursive case calls totalPrice on each subcategory and adds the result to the running total.

Walking the tree by hand for one branch: totalPrice(electronics) adds 49.99 for its own products, then calls totalPrice(phones) (which returns 1698.0) and totalPrice(laptops) (which returns 1299.0). Total for electronics: 49.99 + 1698.0 + 1299.0 = 3046.99.

This is the kind of problem recursion fits well. Writing it with explicit loops requires managing a worklist of unvisited categories by hand, and that worklist is a stack that the language already provides via function calls.

A second case where the structure fits recursion: walking a folder tree. A store keeps product images in a folder, and that folder has subfolders for each category, which in turn have subfolders for each product. To count or process every image, descend into every subfolder, and the tree depth is unknown.

Below, a folder is modeled with a struct, and recursion counts every image file inside it and in all its subfolders.

Same shape as the category tree. The function counts its own images, then calls itself on each subfolder and adds the result. A for loop alone cannot handle this cleanly: at any folder, every parent folder still pending must be remembered so its other subfolders can be visited later. That memory is what the call stack provides.

The standard library has std::filesystem::recursive_directory_iterator (C++17) for real folder traversal, so this code is rarely written by hand. The pattern is the takeaway: when the data is nested, recursion is shorter and clearer than the iterative equivalent.

Anything written recursively can also be written iteratively (with loops), and vice versa. Picking one over the other is a question of which fits the problem.

For flat sequences (an array, a vector, a range of integers), iteration is usually shorter. The cartTotal recursive function shown earlier does the same job as a one-line for loop:

The loop version does not pile up stack frames, does not need a base case, and reads top to bottom. For flat data, prefer the loop.

For nested or tree-shaped data, recursion is usually shorter. Writing totalPrice for the category tree iteratively means maintaining a worklist:

That works, but the worklist is doing exactly the job the call stack was doing in the recursive version. The iterative version is more code, harder to read, and uses heap memory instead of stack memory. It is also harder to extend: iterative tree traversal that needs to do something both "on the way down" and "on the way back up" is significantly more complex.

When in doubt, ask two questions: does the problem itself have nested structure? And could the depth get larger than a few thousand? If the answer to the first is yes and the answer to the second is no, recursion fits.

Recursion uses the call stack, and the call stack is finite. Recursing too deeply runs the program out of stack space and crashes with an error called a stack overflow. On Linux, this usually prints Segmentation fault (core dumped). On Windows, the program may terminate without a clear message.

Two ways to hit a stack overflow:

The first is forgetting the base case (or writing a base case that is never reached). The function then recurses forever, adding a frame every call, until the stack is full.

This prints numbers as fast as it can and eventually crashes. The crash typically happens after tens or hundreds of thousands of calls, depending on the stack size and how large each frame is.

The second way is correct recursion on input that is too deep. The base case is fine and will eventually be reached, but only after, say, a million levels. The stack runs out before that happens.

This is a correct recursive function. The base case (n == 0) is reachable, the recursion makes progress (n - 1 is smaller than n), and the math is right. But a million stack frames will overflow most systems.

The practical depth limit for C++ recursion is a few thousand to a few tens of thousands of frames, depending on the platform and how much each frame uses. If input could push past that, switch to iteration or restructure the recursion. There is no portable way to "ask for more stack" at runtime.

The fix for the sumTo example is to use a loop:

A loop handles a million iterations easily. The loop version has constant memory use regardless of n.

So far every example has been direct recursion: a function calls itself. There is also indirect recursion, where two or more functions call each other in a cycle. Function A calls B, and B (sometimes, somewhere) calls A back. The result is still recursion, because some call eventually leads to a call of the original function.

A small example. A store has products and reviews. Each product has a list of reviews, and each review can quote (link to) another product, and that product has its own reviews, and so on. Computing the total length of all linked text starting from a product looks like this:

productTextLength calls reviewTextLength, which calls productTextLength, which calls reviewTextLength, and so on, until the chain of quoted products bottoms out. Both functions are recursive together, even though neither calls itself directly.

Two practical notes. First, forward declaration matters: the compiler reads top to bottom, so productTextLength needs to know that reviewTextLength exists before it can call it. That is what the line int reviewTextLength(const Review& review); near the top is for. Second, the same base-case discipline applies: if every product has reviews and every review quotes a product, the chain never bottoms out and the result is a stack overflow.

Indirect recursion appears in parsers (where parsing an expression involves parsing terms, and parsing terms involves parsing expressions), state machines, and any situation where two domains reference each other.

A recursive call is in tail position when it is the last thing the function does before returning. No further computation happens after the recursive call comes back; the function returns whatever the recursive call returned.

Compare these two versions of summing a list of prices:

In sumPrices, after the recursive call returns, there is still a + to do. The current frame has to stay alive to remember the value of prices[i] until the recursive call finishes. In sumPricesTail, after the recursive call returns, there is nothing left to do. The current frame is useless once the call happens.

Some languages, like Scheme, guarantee that tail-recursive calls reuse the current stack frame instead of pushing a new one. That turns recursion into iteration, with constant stack space. C++ does not guarantee this. Some compilers, like recent g++ and clang++ at -O2, perform tail call optimization when they can prove it is safe. Others do not. The C++ standard does not require it, so it cannot be relied on.

Writing C++ recursion as if tail call optimization will happen is risky. If the recursion could be deep enough to overflow the stack, rewrite it as a loop. Do not rely on the compiler.

Tail call optimization in C++ is a compiler favor, not a guarantee. Code that relies on it for correctness (to avoid stack overflow) will break on compilers that do not optimize, or on the same compiler with different flags. Convert deep tail recursion to a loop by hand.

Recursion lessons sometimes start with factorial: n! = n * (n - 1)! with 0! = 1. It is a textbook favorite because it has the shape for showing base case and recursive case. Here it is, for context:

Base case n == 0 returns 1. Recursive case multiplies n by the factorial of the smaller number. It is a clear illustration of the two parts, and it traces easily: 5 * 4 * 3 * 2 * 1 * 1 = 120. Factorial is usually written as a loop, because the math is linear and a loop is shorter. Factorial is mentioned because it appears in interviews and other materials.

One trap to know about. Some recursive functions call themselves more than once per call. If each call spawns two more calls, the work doubles at every level. After N levels the total work is 2^N, which grows quickly.

A naive recursive function for "how many ways can a customer split N coupons across 2 carts" looks like this:

For splitWays(40), this function makes over a hundred million calls, because most subproblems are computed many times over. Adding one to the input roughly doubles the work.

A recursive function that makes two self-calls per invocation does O(2^N) work in the worst case. For N = 30, that is around a billion calls. For N = 40, around a trillion. Either restructure the recursion to avoid duplicate work, or switch to a loop.

The fix for this kind of repeated work is a technique called memoization (caching results), covered when this course gets to algorithms. The lesson for now: if a recursive function calls itself multiple times per invocation, walk through how the call count grows before trusting it.

Three patterns to watch for, all of which crash or misbehave in characteristic ways.

Missing or unreachable base case. The function recurses forever and overflows the stack. Symptoms: program prints output very fast (or none at all), then exits with Segmentation fault or no error message. The fix is to write the base case first, before the recursive case, and verify that every recursive call moves toward it.

Starting at n = 0, the recursive call uses n = -1, which hits the base case. Starting at n = 5, the recursion goes 5, 4, 3, 2, 1, 0, -1, hits the base case at -1, and returns. This version works by luck. The clearer version is:

Using < instead of == for the base case is more forgiving. If the input ever drifts past the exact value (because of a step that is not 1, or input that comes in negative), the base case still catches it.

Recursive call does not make progress. Each call passes the same argument, or an argument that does not move toward the base case. Symptoms: same as a missing base case (infinite recursion). The fix is to make sure each recursive call uses a smaller, simpler version of the input.

The base case exists, but sumDown(n) calls sumDown(n), which calls sumDown(n), and so on. The argument never changes, so n never reaches 0.

Reading or writing past the end of a container. The recursion's "smaller problem" is encoded as an index into an array or vector, and the base case is checked too late. Symptoms: undefined behavior, possibly a crash, possibly garbage values without warning.

The base case is reached eventually, but only after reading one element past the end of the vector. The fix is to check the base case first, before any access into the container.