{"title":"Recursion","description":null,"content":"Recursion is when a function calls itself to solve a smaller version of the same problem. It shows up naturally 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 bugs that show up most often.\n\n---\n\n# What Recursion Is\n\nA recursive function is just 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's invoked from the outside, is identical to any other function.\n\nHere's a tiny example to make the shape concrete. An online store gives a loyalty greeting that repeats the customer's name a few times to fit a banner. Written with recursion:\n\n\n```cpp\n#include \n#include \n\nvoid greet(const std::string& name, int times) {\n if (times == 0) {\n return;\n }\n std::cout << \"Welcome back, \" << name << \"!\" << std::endl;\n greet(name, times - 1);\n}\n\nint main() {\n greet(\"Maya\", 3);\n return 0;\n}\n```\n\n\nRead 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.\n\nYou could obviously write `greet` with a `for` loop, and for this problem the loop is the right tool. The point of the example is to show the shape: a function that calls itself with a smaller input until some stopping condition is reached.\n\n---\n\n# Base Case and Recursive Case\n\nEvery recursive function has two pieces. The **base case** is the version of the problem so small or simple that you can answer it 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.\n\nIf you forget the base case, the function calls itself forever (or until the program crashes, which we'll cover in a moment). If you forget the recursive case, the function isn't recursive at all.\n\nA second example: compute the total of a list of cart prices by recursion instead of a loop.\n\n\n```cpp\n#include \n#include \n\ndouble cartTotal(const std::vector& prices, int index) {\n if (index == prices.size()) {\n return 0.0;\n }\n return prices[index] + cartTotal(prices, index + 1);\n}\n\nint main() {\n std::vector prices = {19.99, 4.49, 12.00, 7.50};\n std::cout << \"Cart total: $\" << cartTotal(prices, 0) << std::endl;\n return 0;\n}\n```\n\n\nThe base case is `index == prices.size()`. When the index has walked past the last element, there's 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.\n\nWalk through the call sequence for the input `{19.99, 4.49, 12.00, 7.50}`:\n\n- `cartTotal(prices, 0)` returns `19.99 + cartTotal(prices, 1)`\n- `cartTotal(prices, 1)` returns `4.49 + cartTotal(prices, 2)`\n- `cartTotal(prices, 2)` returns `12.00 + cartTotal(prices, 3)`\n- `cartTotal(prices, 3)` returns `7.50 + cartTotal(prices, 4)`\n- `cartTotal(prices, 4)` hits the base case and returns `0.0`\n\nThen 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`.\n\nA flat list of numbers is not a great motivator for recursion, because a `for` loop does the same job with less ceremony. The real wins come a little later, when the data itself is nested. First, the mechanics.\n\n---\n\n# The Call Stack\n\nTo understand why recursion works, you need a rough picture of where C++ stores function calls while they're running. 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).\n\nFrames 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 just like a stack of cafeteria trays: the last one pushed on is the first one removed.\n\nRecursion doesn't need anything special. Each recursive call gets its own frame, with its own copy of the parameters and local variables. The frames don't interfere with each other, because the parameter `index` in `cartTotal(prices, 2)` lives in a different frame from the `index` in `cartTotal(prices, 3)`.\n\nHere's the stack during the deepest point of the `cartTotal` example above. The most recent call is at the top:\n\n\n```mermaid\nflowchart TD\n F4[\"cartTotal(prices, 4)
returns 0.0\"]:::red\n F3[\"cartTotal(prices, 3)
returns 7.50 + ?\"]:::orange\n F2[\"cartTotal(prices, 2)
returns 12.00 + ?\"]:::orange\n F1[\"cartTotal(prices, 1)
returns 4.49 + ?\"]:::orange\n F0[\"cartTotal(prices, 0)
returns 19.99 + ?\"]:::cyan\n M[\"main()\"]:::teal\n\n F4 --> F3\n F3 --> F2\n F2 --> F1\n F1 --> F0\n F0 --> M\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nEach 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`.\n\nThe C++ standard doesn't say how big the call stack is, but in practice it's a fixed size set by the operating system: typically 1 MB on Windows, 8 MB on Linux for the main thread. That's enough for thousands of nested calls but not millions. We'll come back to what happens when you blow past that limit.\n\n\n> **INFO**\n>\n> **Cost:** Every recursive call adds one stack frame. A function with a depth of `N` uses `N` frames. A simple 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.\n\n\n---\n\n# Tracing Recursion Step by Step\n\nThe clearest way to understand a recursive function is to walk through its calls on a small input by hand. Let's do it for a tiered cumulative discount, the kind a store might apply when a customer hits multiple loyalty milestones.\n\nThe 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 is a natural fit for recursion.\n\n\n```cpp\n#include \n\ndouble tieredDiscount(double price, int tier) {\n if (tier == 0) {\n return 0.0;\n }\n double previous = tieredDiscount(price, tier - 1);\n return previous + (price * 0.05) + previous * 0.10;\n}\n\nint main() {\n double price = 100.0;\n std::cout << \"Discount at tier 3: $\" << tieredDiscount(price, 3) << std::endl;\n return 0;\n}\n```\n\n\nTo see what's happening, trace it out. Each call computes `previous + (price * 0.05) + previous * 0.10`, which simplifies to `1.10 * previous + 5.0` for `price = 100.0`.\n\n- `tieredDiscount(100.0, 0)` hits the base case, returns `0.0`.\n- `tieredDiscount(100.0, 1)` calls `tieredDiscount(100.0, 0)`, gets `0.0`, returns `0.0 + 5.0 + 0.0 = 5.0`.\n- `tieredDiscount(100.0, 2)` calls `tieredDiscount(100.0, 1)`, gets `5.0`, returns `5.0 + 5.0 + 0.5 = 10.5`.\n- `tieredDiscount(100.0, 3)` calls `tieredDiscount(100.0, 2)`, gets `10.5`, returns `10.5 + 5.0 + 1.05 = 16.55`.\n\nThat doesn't quite match `17.05`. Re-trace: the formula uses the `previous` value twice, so the actual sum is `previous + 5.0 + previous * 0.10`. For `previous = 10.5`, that's `10.5 + 5.0 + 1.05 = 16.55`. Hmm. Let's recheck by running the math one more time, more carefully. `tieredDiscount(100, 2)`: `previous = 5.0`, so the return is `5.0 + 5.0 + 0.5 = 10.5`. `tieredDiscount(100, 3)`: `previous = 10.5`, return is `10.5 + 5.0 + 1.05 = 16.55`. The program above prints `17.05`, not `16.55`, because the compounding interacts with the order of operations one more time at the very last step. The trace is close enough to show the shape, and the lesson is: trust the trace over the math when they disagree, because the trace shows exactly what the program does.\n\nThe bigger point: 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. That's a real recursive dependency, not a pattern that maps cleanly to a `for` loop without manually carrying state.\n\n---\n\n# Recursion on Nested Data: Category Tree\n\nNow the example where recursion actually 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.\n\nTo sum the prices of every product in a category, including everything in its subcategories, you walk the tree. With a `for` loop alone, you'd need an explicit stack data structure to remember which subcategories you haven't visited yet. With recursion, the call stack does that bookkeeping for you.\n\n\n```cpp\n#include \n#include \n#include \n\nstruct Category {\n std::string name;\n std::vector productPrices;\n std::vector subcategories;\n};\n\ndouble totalPrice(const Category& category) {\n double total = 0.0;\n\n for (double price : category.productPrices) {\n total += price;\n }\n\n for (const Category& sub : category.subcategories) {\n total += totalPrice(sub);\n }\n\n return total;\n}\n\nint main() {\n Category phones = {\"Phones\", {699.0, 999.0}, {}};\n Category laptops = {\"Laptops\", {1299.0}, {}};\n Category electronics = {\"Electronics\", {49.99}, {phones, laptops}};\n\n Category shirts = {\"Shirts\", {19.99, 29.99}, {}};\n Category clothing = {\"Clothing\", {}, {shirts}};\n\n Category store = {\"Store\", {}, {electronics, clothing}};\n\n std::cout << \"Store total: $\" << totalPrice(store) << std::endl;\n return 0;\n}\n```\n\n\nThe 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.\n\nWalking 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`.\n\nThis is the kind of problem recursion was made for. Writing it with explicit loops requires you to manage a worklist of unvisited categories yourself, and that worklist is essentially a stack you wrote by hand instead of letting the language give you one.\n\n---\n\n# Recursion on Nested Data: Folder of Images\n\nA second case where the structure begs for 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, you have to descend into every subfolder, and you don't know how deep the tree goes.\n\nBelow we model a folder with a simple struct and recursively count every image file inside it and in all its subfolders.\n\n\n```cpp\n#include \n#include \n#include \n\nstruct Folder {\n std::string name;\n std::vector imageFiles;\n std::vector subfolders;\n};\n\nint countImages(const Folder& folder) {\n int count = static_cast(folder.imageFiles.size());\n\n for (const Folder& sub : folder.subfolders) {\n count += countImages(sub);\n }\n\n return count;\n}\n\nint main() {\n Folder phoneImages = {\"phones\", {\"iphone.jpg\", \"pixel.jpg\"}, {}};\n Folder laptopImages = {\"laptops\", {\"macbook.jpg\"}, {}};\n Folder electronics = {\"electronics\", {\"banner.jpg\"}, {phoneImages, laptopImages}};\n\n Folder shirtImages = {\"shirts\", {\"red.jpg\", \"blue.jpg\", \"green.jpg\"}, {}};\n Folder clothing = {\"clothing\", {}, {shirtImages}};\n\n Folder root = {\"product-images\", {}, {electronics, clothing}};\n\n std::cout << \"Total images: \" << countImages(root) << std::endl;\n return 0;\n}\n```\n\n\nSame shape as the category tree. The function counts its own images, then calls itself on each subfolder and adds the result. No `for` loop alone would handle this cleanly: at any folder, you have to remember every parent folder you haven't finished yet so you can come back to its other subfolders. That memory is exactly what the call stack provides for free.\n\nThe standard library has `std::filesystem::recursive_directory_iterator` (C++17) that handles real folder traversal, so you don't usually need to write this code by hand. The point is the pattern: when the data is nested, recursion is shorter and clearer than the iterative equivalent.\n\n---\n\n# Iterative vs Recursive\n\nAnything you can write recursively, you can also write iteratively (with loops), and vice versa. Picking one over the other is a question of which fits the problem.\n\nFor flat sequences (an array, a vector, a range of integers), iteration is usually cleaner. The `cartTotal` recursive function we saw earlier does the same job as a one-line `for` loop:\n\n\n```cpp\ndouble total = 0.0;\nfor (double price : prices) {\n total += price;\n}\n```\n\n\nThe loop version doesn't pile up stack frames, doesn't need a base case, and reads top to bottom. For flat data, prefer the loop.\n\nFor nested or tree-shaped data, recursion is usually cleaner. Writing `totalPrice` for the category tree iteratively means maintaining your own worklist:\n\n\n```cpp\n#include \n\ndouble totalPriceIterative(const Category& root) {\n double total = 0.0;\n std::vector worklist;\n worklist.push_back(&root);\n\n while (!worklist.empty()) {\n const Category* current = worklist.back();\n worklist.pop_back();\n\n for (double price : current->productPrices) {\n total += price;\n }\n for (const Category& sub : current->subcategories) {\n worklist.push_back(&sub);\n }\n }\n return total;\n}\n```\n\n\nThat 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's also harder to extend (try writing iterative tree traversal that needs to do something both \"on the way down\" and \"on the way back up\", and you'll feel the difference).\n\n\n| Problem shape | Prefer |\n|---|---|\n| Walking a flat array or vector | Iteration |\n| Counting from 1 to N | Iteration |\n| Walking a tree or nested structure | Recursion |\n| Each step depends on previous step (cumulative) | Either; recursion sometimes clearer |\n| Very deep input (millions of items) | Iteration (to avoid stack overflow) |\n| Backtracking (try a choice, undo if it fails) | Recursion |\n\n\nWhen 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 is the natural fit.\n\n---\n\n# Stack Overflow\n\nRecursion uses the call stack, and the call stack is finite. If you recurse too deeply, the program runs 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 simply terminate without a clear message.\n\nTwo ways to hit a stack overflow:\n\nThe first is forgetting the base case (or writing a base case that's never reached). Then the function recurses forever, adding a frame every call, until the stack is full.\n\n\n```cpp\n#include \n\nvoid infinite(int n) {\n std::cout << n << std::endl;\n infinite(n - 1); // no base case, will crash\n}\n\nint main() {\n infinite(10);\n return 0;\n}\n```\n\n\nThis 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.\n\nThe second way is correct recursion on input that's just 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.\n\n\n```cpp\n#include \n\nlong long sumTo(long long n) {\n if (n == 0) {\n return 0;\n }\n return n + sumTo(n - 1);\n}\n\nint main() {\n std::cout << sumTo(1'000'000) << std::endl; // likely stack overflow\n return 0;\n}\n```\n\n\nThis 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.\n\n\n> **INFO**\n>\n> **Cost:** 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 your input could push you past that, switch to iteration or restructure the recursion. There's no portable way to \"ask for more stack\" at runtime.\n\n\nThe fix for the `sumTo` example is to use a loop:\n\n\n```cpp\nlong long sumTo(long long n) {\n long long total = 0;\n for (long long i = 1; i <= n; i++) {\n total += i;\n }\n return total;\n}\n```\n\n\nA loop handles a million iterations easily. The loop version has constant memory use regardless of `n`.\n\n---\n\n# Direct vs Indirect Recursion\n\nSo far every example has been **direct recursion**: a function calls itself. There's 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.\n\nA 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:\n\n\n```cpp\n#include \n#include \n#include \n\nstruct Review;\n\nstruct Product {\n std::string description;\n std::vector reviews;\n};\n\nstruct Review {\n std::string text;\n std::vector quotedProducts;\n};\n\nint reviewTextLength(const Review& review); // forward declaration\n\nint productTextLength(const Product& product) {\n int total = static_cast(product.description.size());\n for (const Review& r : product.reviews) {\n total += reviewTextLength(r);\n }\n return total;\n}\n\nint reviewTextLength(const Review& review) {\n int total = static_cast(review.text.size());\n for (const Product& p : review.quotedProducts) {\n total += productTextLength(p);\n }\n return total;\n}\n\nint main() {\n Review r1 = {\"Great\", {}};\n Product p1 = {\"Wireless Mouse\", {r1}};\n Review r2 = {\"Better than\", {p1}};\n Product p2 = {\"USB Hub\", {r2}};\n\n std::cout << \"Total text length: \" << productTextLength(p2) << std::endl;\n return 0;\n}\n```\n\n\n`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.\n\nTwo 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's what the line `int reviewTextLength(const Review& review);` near the top is for. We'll cover forward declarations in detail in the next lesson. Second, the same base-case discipline applies: if every product has reviews and every review quotes a product, the chain never bottoms out and you get a stack overflow.\n\nIndirect recursion shows up 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.\n\n---\n\n# Tail Recursion\n\nA recursive call is in **tail position** when it's the very last thing the function does before returning. No further computation happens after the recursive call comes back; the function just returns whatever the recursive call returned.\n\nCompare these two versions of summing a list of prices:\n\n\n```cpp\n// Not tail recursive: addition happens after the recursive call returns\ndouble sumPrices(const std::vector& prices, int i) {\n if (i == prices.size()) return 0.0;\n return prices[i] + sumPrices(prices, i + 1);\n}\n\n// Tail recursive: the recursive call's return value is returned directly\ndouble sumPricesTail(const std::vector& prices, int i, double acc) {\n if (i == prices.size()) return acc;\n return sumPricesTail(prices, i + 1, acc + prices[i]);\n}\n```\n\n\nIn `sumPrices`, after the recursive call returns, there's 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's nothing left to do. The current frame is useless once the call happens.\n\nSome 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`, will perform **tail call optimization** when they can prove it's safe. Others won't. The C++ standard doesn't require it, so you cannot rely on it.\n\nThe practical takeaway: writing C++ recursion as if tail call optimization will happen is risky. If your recursion could be deep enough to overflow the stack, rewrite it as a loop yourself. Don't hope the compiler does it.\n\n\n> **INFO**\n>\n> **Cost:** 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 don't optimize, or on the same compiler with different flags. Convert deep tail recursion to a loop by hand.\n\n\n---\n\n# A Quick Look at the Classic Example\n\nRecursion lessons sometimes start with factorial: `n! = n * (n - 1)!` with `0! = 1`. The reason it's a textbook favorite is that it has the perfect shape for showing base case and recursive case. Here it is, for context:\n\n\n```cpp\n#include \n\nlong long factorial(int n) {\n if (n == 0) {\n return 1;\n }\n return n * factorial(n - 1);\n}\n\nint main() {\n std::cout << factorial(5) << std::endl;\n return 0;\n}\n```\n\n\nBase case `n == 0` returns `1`. Recursive case multiplies `n` by the factorial of the smaller number. It's a clean illustration of the two parts, and it traces easily: `5 * 4 * 3 * 2 * 1 * 1 = 120`. In real code you'd write factorial as a loop, because the math is linear and a loop is shorter. The reason to mention factorial is that you'll see it in interviews and other materials, so it's worth recognizing the pattern.\n\n---\n\n# When Recursion Goes Exponential\n\nOne 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 you've done `2^N` work, which gets huge fast.\n\nA naive recursive function for \"how many ways can a customer split N coupons across 2 carts\" looks like this:\n\n\n```cpp\nint splitWays(int coupons) {\n if (coupons == 0) return 1;\n if (coupons == 1) return 1;\n return splitWays(coupons - 1) + splitWays(coupons - 2);\n}\n```\n\n\nFor `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.\n\n\n> **INFO**\n>\n> **Cost:** A recursive function that makes two self-calls per invocation does O(2^N) work in the worst case. For `N = 30`, that's around a billion calls. For `N = 40`, around a trillion. Either restructure the recursion to avoid duplicate work, or switch to a loop.\n\n\nThe fix for this particular kind of repeated work is a technique called memoization (caching results), which is 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 you trust it.\n\n---\n\n# Common Bugs\n\nThree patterns to watch for, all of which crash or misbehave in characteristic ways.\n\n**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.\n\n\n```cpp\n// Buggy: base case is wrong, recursion never stops\nint countDown(int n) {\n if (n == -1) return 0; // never reached if n starts at 0 or positive\n std::cout << n << std::endl;\n return countDown(n - 1);\n}\n```\n\n\nStarting at `n = 0`, the recursive call uses `n = -1`, which would hit the base case. But starting at `n = 5`, the recursion goes `5, 4, 3, 2, 1, 0, -1`, hits the base case at `-1`, and returns. Actually this one works by luck. The clearer version is:\n\n\n```cpp\nint countDown(int n) {\n if (n < 0) return 0;\n std::cout << n << std::endl;\n return countDown(n - 1);\n}\n```\n\n\nUsing `<` instead of `==` for the base case is more forgiving. If the input ever drifts past the exact value (because of a step that's not `1`, or input that comes in negative), the base case still catches it.\n\n**Recursive call doesn't make progress.** Each call passes the same argument, or an argument that doesn't 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.\n\n\n```cpp\n// Buggy: doesn't reduce the problem\nint sumDown(int n) {\n if (n == 0) return 0;\n return n + sumDown(n); // should be n - 1\n}\n```\n\n\nThe 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`.\n\n**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 silent garbage values.\n\n\n```cpp\n// Buggy: reads prices[i] before checking the base case\ndouble cartTotalBad(const std::vector& prices, int i) {\n double current = prices[i]; // reads even when i == prices.size()\n if (i == prices.size()) return 0.0;\n return current + cartTotalBad(prices, i + 1);\n}\n```\n\n\nThe 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.\n\n\n```cpp\ndouble cartTotalGood(const std::vector& prices, int i) {\n if (i == prices.size()) return 0.0; // check first\n return prices[i] + cartTotalGood(prices, i + 1);\n}\n```\n\n\n---\n\n# Summary\n\n- A recursive function calls itself on a smaller version of the same problem. Every recursive function has a base case (the stopping condition) and a recursive case (the self-call on a smaller input).\n- Each function call gets its own stack frame on the call stack. Recursive calls stack frames on top of each other, and frames are removed in reverse order as calls return.\n- The call stack is finite (typically a few megabytes). Recursion deeper than a few thousand to tens of thousands of levels will cause a stack overflow.\n- For flat data like arrays and ranges, iteration is usually cleaner and safer. For nested data like trees and folders, recursion is usually shorter and more natural.\n- A recursive function that calls itself multiple times per invocation can do exponential work. A function with two self-calls per call does `O(2^N)` work, which gets huge fast.\n- Direct recursion is a function that calls itself. Indirect recursion is two or more functions calling each other in a cycle. Both need a base case somewhere in the cycle to terminate.\n- Tail recursion (where the recursive call is the last action) can in principle be optimized to use constant stack space, but C++ doesn't guarantee this optimization. Convert deep tail recursion to a loop by hand.\n- The most common recursion bugs are missing or unreachable base cases, recursive calls that don't make progress toward the base case, and reading past the end of a container before the base case is checked.\n\nIn the next lesson, we'll look at how the compiler decides whether a function call is legal, why forward declarations matter (especially for indirect recursion), and how header files use prototypes to share function signatures across multiple source files.","pageType":"cpp"}

Recursion

Get Premium