{"title":"Recursion","description":"","content":"Some problems are easier to describe in terms of themselves. The total price of a shopping cart is the price of the first item plus the total of the rest. A bundle's price is the sum of its products plus the prices of any sub-bundles inside it. When the shape of the problem repeats at a smaller size, the most direct way to write the solution often repeats too. A method that calls itself is called a recursive method, and recursion is the name we give that style of solving problems.\n\nThis lesson covers what recursion is, the two parts every recursive method needs, how the call stack tracks all those calls, and when recursion fits versus when a loop would do better.\n\n---\n\n# What Recursion Is\n\nA recursive method is a method that calls itself. That's the whole definition. Java doesn't have special syntax for recursion. Any method can call any other method, including itself, and the compiler doesn't treat the call any differently.\n\nThe smallest recursive method that does something useful: It counts down from a number to zero.\n\n\n```java\npublic class CountDown {\n public static void countDown(int n) {\n if (n < 0) {\n return;\n }\n System.out.println(n);\n countDown(n - 1);\n }\n\n public static void main(String[] args) {\n countDown(3);\n }\n}\n```\n\n\nThe method prints `n`, then calls itself with `n - 1`. Each call prints one number and triggers the next call with a smaller argument. When `n` reaches `-1`, the `if` check sends control back through the `return` and the chain stops.\n\nTwo things make this work. The method gets smaller input each time it calls itself, so it's moving toward a stopping point. And there's an explicit check that handles the stopping point without making another call. Take either of those away and the program either runs forever or never produces an answer.\n\n---\n\n# Base Case and Recursive Case\n\nEvery recursive method has the same shape. There's a check at the top that says \"if the input is small enough, just return the answer directly\". That's the base case. Everything else is a step that reduces the problem and then calls the method again on the smaller version. That's the recursive case.\n\nA slightly more interesting example is `factorial`. The factorial of `n` is `n * (n-1) * (n-2) * ... * 1`. We need this kind of counting in an online store any time we want to know how many ways a small set of items can be arranged. Three items in a \"bestseller bundle\" can sit in `3! = 6` different orders on the product page. Five items can sit in `5! = 120` orders. Factorials grow fast.\n\n\n```java\npublic class Factorial {\n public static int factorial(int n) {\n if (n <= 1) {\n return 1;\n }\n return n * factorial(n - 1);\n }\n\n public static void main(String[] args) {\n System.out.println(\"3! = \" + factorial(3));\n System.out.println(\"5! = \" + factorial(5));\n System.out.println(\"7! = \" + factorial(7));\n }\n}\n```\n\n\nThe `if (n <= 1)` check is the base case. When `n` is `0` or `1`, the answer is just `1` and we return it directly. The line `return n * factorial(n - 1)` is the recursive case. It expresses the rule \"factorial of `n` equals `n` times factorial of `n - 1`\" almost word for word.\n\nThe base case is what makes the method finish. Without it, the recursive calls keep going and each one calls the next on a smaller and smaller number, then on negative numbers, and the chain has nothing to stop it. Recursion without a base case is the same kind of bug as a `while` loop with a condition that never becomes false.\n\nEvery recursive call uses a fresh stack frame, which costs both memory and time.\n\n---\n\n# What Happens Without a Base Case\n\nIf the base case is missing or wrong, the method calls itself forever. Java doesn't let that go on indefinitely. Each call consumes a chunk of stack memory, and once the stack is full the JVM throws a `StackOverflowError` and the program crashes.\n\n\n```java\npublic class NoBaseCase {\n public static int countOrders(int n) {\n // Bug: no base case\n return 1 + countOrders(n - 1);\n }\n\n public static void main(String[] args) {\n System.out.println(countOrders(5));\n }\n}\n```\n\n\nThe stack trace prints the same line over and over because the method keeps calling itself from the same spot. That repeated pattern is a strong signal that you have runaway recursion.\n\nA base case that the input never reaches has the same problem. If `factorial` checked `n == 0` but you called it with a negative number, `n` would decrease past zero and the method would never stop. Pick a base case that the recursive calls actually move toward.\n\n---\n\n# The Call Stack\n\nTo understand recursion deeply, you have to understand what Java is doing internally. Every time a method is called, the JVM creates a stack frame for that call. The frame holds the method's local variables, its parameters, and a return address that tells the JVM where to continue when the method finishes. Frames stack on top of each other like a pile of trays. The newest call sits on top. When a method returns, its frame is removed and control resumes in the frame below it.\n\nFor ordinary methods this is invisible. For recursive methods, the stack becomes the whole story. Each recursive call adds another frame, and the frames don't go away until the chain unwinds.\n\nWalk through `factorial(3)` one step at a time. The first call is `factorial(3)`. Since `3 > 1`, it has to compute `3 * factorial(2)`. To get that, it pauses and calls `factorial(2)`. That pauses too and calls `factorial(1)`. Now `1 <= 1`, so `factorial(1)` returns `1` without making another call. Control returns to `factorial(2)`, which finishes its multiplication and returns `2 * 1 = 2`. Control returns to `factorial(3)`, which finishes and returns `3 * 2 = 6`.\n\nThe diagram below shows the stack frames in two phases. The top half shows the stack growing as each call is added. The bottom half shows it shrinking as each call returns.\n\n\n```mermaid\nflowchart TD\n subgraph Growing [Stack grows as calls are made]\n direction TB\n G1[factorial 3
waiting for factorial 2]:::cyan\n G2[factorial 2
waiting for factorial 1]:::orange\n G3[factorial 1
base case, returns 1]:::green\n G1 --> G2\n G2 --> G3\n end\n\n subgraph Shrinking [Stack shrinks as calls return]\n direction TB\n S3[factorial 1 returns 1]:::green\n S2[factorial 2 returns 2 times 1 = 2]:::orange\n S1[factorial 3 returns 3 times 2 = 6]:::cyan\n S3 --> S2\n S2 --> S1\n end\n\n Growing --> Shrinking\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe growing phase is where the work is set up. The shrinking phase is where the answers flow back. Each frame holds its own value of `n`. When `factorial(2)` is paused, its `n` is `2`, even though `factorial(1)` is running with `n = 1` on top of it. Local variables in a paused frame are protected from anything happening above it.\n\nTwo practical points fall out of this. First, recursion uses memory proportional to its depth. If you recurse a thousand times, a thousand frames sit on the stack at once. Second, the order of work runs forward through the calls and backward through the returns. The deepest call runs first to completion. Then each call above it finishes in turn.\n\n---\n\n# Summing Prices in a Cart\n\nA cart total is a clean recursive problem. The sum of the first `n` prices is the first price plus the sum of the remaining `n - 1`. The base case is an empty range, which sums to zero.\n\n\n```java\npublic class CartSum {\n public static double sumPrices(double[] prices, int index) {\n if (index == prices.length) {\n return 0.0;\n }\n return prices[index] + sumPrices(prices, index + 1);\n }\n\n public static void main(String[] args) {\n double[] prices = {29.99, 9.99, 14.50, 4.99};\n double total = sumPrices(prices, 0);\n System.out.println(\"Cart total: $\" + total);\n }\n}\n```\n\n\nThe parameter `index` is the trick. It marks where we are in the array. Each recursive call moves one step to the right by passing `index + 1`. When `index` reaches `prices.length`, there's nothing left to add, so the method returns `0.0`.\n\nThis works, but for a flat list a `for` loop does the same job with less ceremony.\n\n\n```java\npublic class CartSumLoop {\n public static void main(String[] args) {\n double[] prices = {29.99, 9.99, 14.50, 4.99};\n double total = 0.0;\n for (double price : prices) {\n total += price;\n }\n System.out.println(\"Cart total: $\" + total);\n }\n}\n```\n\n\nThe loop is shorter, uses no extra stack memory, and reads in a straight line. For a flat array, recursion is overkill.\n\n---\n\n# Nested Bundles: Where Recursion Shines\n\nA bundle in an online store can contain individual products, and it can also contain other bundles. A \"Home Office\" bundle might include a desk, a chair, and a smaller \"Stationery\" bundle that itself contains pens, a notebook, and a stapler. There's no fixed depth. A bundle can contain a bundle that contains a bundle, and so on.\n\nComputing the total price of a bundle is a problem that's naturally recursive because the structure is naturally recursive. The price of a bundle is the sum of the prices of its contents, and each \"content\" is either a product (a flat price) or another bundle (whose price we compute the same way).\n\n\n```java\npublic class BundlePricing {\n public static double priceOf(Object item) {\n if (item instanceof Double price) {\n return price;\n }\n if (item instanceof Object[] bundle) {\n double total = 0.0;\n for (Object content : bundle) {\n total += priceOf(content);\n }\n return total;\n }\n return 0.0;\n }\n\n public static void main(String[] args) {\n Object stationery = new Object[]{2.49, 5.99, 7.50};\n Object homeOffice = new Object[]{199.00, 89.50, stationery};\n Object megaBundle = new Object[]{homeOffice, 19.99};\n\n System.out.println(\"Stationery total: $\" + priceOf(stationery));\n System.out.println(\"Home Office total: $\" + priceOf(homeOffice));\n System.out.println(\"Mega Bundle total: $\" + priceOf(megaBundle));\n }\n}\n```\n\n\nTwo base cases, one recursive case. If the item is a `Double`, return it directly. If the item is an array of pieces, walk the array and recursively price each piece. The recursion descends naturally into nested bundles without us having to know the depth in advance.\n\nTry writing this with loops alone. You'd need a stack or queue to track the bundles you haven't expanded yet, and you'd be reimplementing what the call stack already does. Recursion lets the language manage the bookkeeping for you.\n\nEach recursive call adds a stack frame. For nested bundles that go a few levels deep, the cost is trivial. For a structure thousands of levels deep, you'd run out of stack space. Recursion is best when the depth is naturally bounded.\n\nThe same shape solves any tree-like structure. Category trees in a catalog (Electronics contains Audio contains Headphones), comments with replies that have replies of their own, file system directories that contain other directories. Anywhere the data is \"a thing or a collection of things\", recursion fits.\n\n---\n\n# Tracing a Recursive Call\n\nWhen recursion is misbehaving, the fastest way to find the problem is to trace the calls by hand. Pretend you're the JVM. For each call, write down the value of every parameter and what the method returns.\n\nA trace for `factorial(4)`:\n\n\n```shell\nfactorial(4)\n calls factorial(3)\n calls factorial(2)\n calls factorial(1)\n n <= 1, returns 1\n returns 2 * 1 = 2\n returns 3 * 2 = 6\n returns 4 * 6 = 24\n```\n\n\nThe indent shows the depth. Each level adds two spaces. Calls open downward, returns close upward. If a return is wrong, you can spot which level produced it because the values are right there in the trace.\n\nFor something a bit larger, `sumPrices` from the cart example, called with `prices = {10.0, 20.0, 30.0}` and `index = 0`:\n\n\n```shell\nsumPrices([10, 20, 30], 0)\n calls sumPrices([10, 20, 30], 1)\n calls sumPrices([10, 20, 30], 2)\n calls sumPrices([10, 20, 30], 3)\n index == length, returns 0.0\n returns 30.0 + 0.0 = 30.0\n returns 20.0 + 30.0 = 50.0\n returns 10.0 + 50.0 = 60.0\n```\n\n\nA trace this short can fit on paper. For deeper recursion, a few `System.out.println` calls at the top and bottom of the method do the same thing without the writing.\n\n---\n\n# Tail Recursion and Why Java Doesn't Optimize It\n\nA tail-recursive method is one where the recursive call is the very last thing the method does. The call's return value is returned directly without any extra work after it.\n\nCompare these two. The first is not tail-recursive. After the recursive call returns, the method still has to multiply by `n` before returning.\n\n\n```java\npublic static int factorial(int n) {\n if (n <= 1) {\n return 1;\n }\n return n * factorial(n - 1); // multiplication happens after the call\n}\n```\n\n\nThe second version rewrites it to be tail-recursive by passing the running result as a parameter.\n\n\n```java\npublic static int factorialTail(int n, int accumulator) {\n if (n <= 1) {\n return accumulator;\n }\n return factorialTail(n - 1, n * accumulator); // call is the last operation\n}\n```\n\n\nHere the recursive call's return value is the method's return value with nothing else done to it. Some languages, like Scala, Kotlin, and Scheme, recognize this pattern and reuse the current stack frame for the recursive call. That makes the recursion run in constant stack space, just like a loop.\n\nJava does not. The JVM's specification allows tail-call optimization, but the standard javac compiler and HotSpot runtime don't implement it. A tail-recursive Java method uses the same amount of stack space as a non-tail-recursive one. Calling `factorialTail(10000, 1)` will throw `StackOverflowError` for the same reason `factorial(10000)` would.\n\nThe practical takeaway: in Java, the shape of a recursive method doesn't affect its stack usage. If you need a method to handle deep input without crashing, convert it to a loop.\n\n---\n\n# Stack Overflow and How to Avoid It\n\nEach stack frame takes up some bytes of memory. The exact size depends on the method's parameters and local variables, but a few dozen to a few hundred bytes per frame is typical. The total stack space available to a thread on a 64-bit JVM defaults to about 512 KB on macOS and Linux and 1 MB on Windows, though the exact number varies by version and platform. That gives you somewhere in the neighborhood of a few thousand to a few tens of thousands of frames before you run out.\n\nFor shallow recursion, that's plenty. A bundle nested fifteen levels deep won't come close to the limit. A binary tree traversal on a balanced tree of a million nodes has a depth of about twenty, also fine. Where you get into trouble is recursion whose depth grows linearly with the input size, like the `sumPrices` example above. Run that on an array of a million prices and it crashes.\n\n\n```java\npublic class DeepSum {\n public static long sumTo(long n) {\n if (n == 0) {\n return 0;\n }\n return n + sumTo(n - 1);\n }\n\n public static void main(String[] args) {\n System.out.println(sumTo(100_000));\n }\n}\n```\n\n\nA loop has no such limit. It uses one stack frame regardless of how many iterations it runs.\n\n\n```java\npublic class DeepSumLoop {\n public static void main(String[] args) {\n long sum = 0;\n for (long i = 1; i <= 100_000; i++) {\n sum += i;\n }\n System.out.println(sum);\n }\n}\n```\n\n\nWhen a recursive method's depth is unbounded or grows with input size, rewrite it as a loop. When the depth is naturally small and the structure is recursive (trees, nested bundles), keep the recursion. The rule of thumb is depth, not the number of operations. A recursion that runs a million times but only nests fifteen frames deep is fine. A recursion that nests a million frames deep is not.\n\nA `StackOverflowError` doesn't always mean the recursion is wrong. Sometimes the algorithm is correct but the input is bigger than the stack can hold. Either bound the depth, switch to iteration, or, as a last resort, run the work on a thread with a larger stack via `new Thread(runnable, \"name\", largerStackSize)`.\n\n---\n\n# Recursion vs Iteration\n\nThe same problem can usually be solved both ways. The choice comes down to which version reads more clearly and whether the depth is bounded.\n\n\n```mermaid\nflowchart LR\n subgraph Recursion\n direction TB\n R1[Define base case]:::cyan\n R2[Define recursive case]:::cyan\n R3[Each call uses
a new stack frame]:::orange\n R4[Stack depth equals
recursion depth]:::orange\n R1 --> R2 --> R3 --> R4\n end\n\n subgraph Iteration\n direction TB\n I1[Initialize variables]:::green\n I2[Loop with condition]:::green\n I3[Update inside loop]:::teal\n I4[Constant stack memory]:::teal\n I1 --> I2 --> I3 --> I4\n end\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nA table makes the trade-offs concrete.\n\n\n| Aspect | Recursion | Iteration |\n| ------ | --------- | --------- |\n| Memory | One stack frame per call | One stack frame total |\n| Speed | Slower due to call overhead | Faster, no call overhead |\n| Readability | Better for tree-shaped problems | Better for sequential problems |\n| Risk | `StackOverflowError` on deep input | Infinite loop if condition is wrong |\n| State | Held in parameters and local variables | Held in mutable variables |\n| Best for | Trees, nested structures, divide and conquer | Counters, sequential scans, fixed iteration |\n\n\nThe summary: pick recursion when the data is recursive. Pick iteration when the work is sequential. If both fit, pick whichever reads more clearly, and switch to iteration only if depth becomes a problem.\n\n---\n\n# When to Use Recursion\n\nRecursion is well-suited when the problem fits one of these shapes:\n\n- **Tree or graph traversal.** Walking a category tree, a comment thread, a directory structure, or an HTML document. The structure is recursive, so the code matches.\n- **Nested data.** Bundles that contain bundles. JSON objects with nested objects. The depth is unknown and the same operation applies at every level.\n- **Divide and conquer.** Splitting a problem into smaller versions of itself and combining the answers. Classic examples are binary search, merge sort, and quicksort, which we cover in the data structures and algorithms course.\n- **Problems naturally defined recursively.** Factorial, Fibonacci, computing the number of ways to arrange items. The math itself uses self-reference, and the code follows.\n\nCases where recursion is overkill or actively wrong:\n\n- **Sequential work over a flat collection.** Use a `for` loop.\n- **Counting up to a fixed number.** Use a `for` loop.\n- **Anything where the depth grows linearly with input size.** The risk of `StackOverflowError` isn't worth it.\n\nA useful mental model is to ask: does the problem describe itself in terms of smaller versions of the same problem? If yes, recursion fits. If the answer is \"no, it's a series of steps from start to finish\", a loop fits.\n\n---\n\n# A Tree Traversal Example\n\nTo close out the recursion-fits-the-data idea, a small category tree. Categories are nested. Each category has a name and a list of subcategories. To print every category name in the tree, you can write the traversal in three lines.\n\n\n```java\nimport java.util.List;\n\npublic class CategoryTree {\n record Category(String name, List subcategories) {}\n\n public static void printAll(Category category, int depth) {\n System.out.println(\" \".repeat(depth) + category.name());\n for (Category sub : category.subcategories()) {\n printAll(sub, depth + 1);\n }\n }\n\n public static void main(String[] args) {\n Category headphones = new Category(\"Headphones\", List.of());\n Category speakers = new Category(\"Speakers\", List.of());\n Category audio = new Category(\"Audio\", List.of(headphones, speakers));\n\n Category laptops = new Category(\"Laptops\", List.of());\n Category computers = new Category(\"Computers\", List.of(laptops));\n\n Category electronics = new Category(\"Electronics\", List.of(audio, computers));\n\n printAll(electronics, 0);\n }\n}\n```\n\n\nThe base case isn't an explicit `if` here. When a category has an empty `subcategories` list, the `for` loop runs zero times and the method returns without making any more calls. The recursion handles arbitrary depth without us writing any depth-tracking logic. The `depth` parameter is just for indentation, not for the algorithm itself.\n\nThis is the pattern recursion fits. The data is a tree. The traversal is a tree walk. Each piece of code mirrors a piece of the structure.","pageType":"java"}

Recursion

Get Premium