{"title":"Recursion","description":"","content":"Recursion is when a function calls itself to solve a smaller version of the same problem. It's the natural way to work with nested or tree-shaped data, where each piece of the structure looks like the whole. This lesson covers what recursion is, the two parts every recursive function has, how Python actually runs recursive calls, where recursion shines and where it falls over, and the limits Python places on it.\n\n---\n\n# What Recursion Is\n\nA recursive function is one whose body calls itself, but with smaller or simpler input. The idea is to break a problem into a piece you can solve directly and a smaller version of the same problem, then trust the function to handle that smaller version.\n\nCounting down from a number is the simplest example that shows the shape without doing real work:\n\n\n```python\ndef countdown(n):\n if n == 0:\n print(\"done\")\n return\n print(n)\n countdown(n - 1)\n\ncountdown(3)\n```\n\n\nThe function prints `n`, then calls itself with `n - 1`. Each call has a smaller number than the last, until `n` reaches `0`, at which point the function prints `\"done\"` and stops calling itself.\n\nThat's the whole pattern. Two questions to ask of any recursive function:\n\n1. What's the simplest case it can answer directly, without calling itself?\n2. How does each call shrink the problem so it moves toward that simplest case?\n\nIf the answer to either question is unclear, the recursion is broken. Either it never stops (infinite recursion), or it stops on the wrong case, or it grows the problem instead of shrinking it.\n\nA useful mental model: a recursive function is a description, not a procedure. You describe what the answer is in terms of a smaller answer, and Python does the unfolding for you. `countdown(3)` is `print(3)` followed by `countdown(2)`, which is `print(2)` followed by `countdown(1)`, and so on. You wrote the rule once. Python applied it four times.\n\nA more useful e-commerce flavored example. Suppose a cart is a flat list of prices, and you want to add them up without using `sum()`:\n\n\n```python\ndef cart_total(prices):\n if not prices:\n return 0.0\n return prices[0] + cart_total(prices[1:])\n\ncart = [29.99, 14.99, 9.99, 4.99]\nprint(f\"${cart_total(cart):.2f}\")\n```\n\n\nThe two ingredients are visible. An empty list has total `0.0`, which the function returns directly. Any non-empty list is \"the first price, plus the total of the rest\". The \"rest\" is a smaller list, so the recursive call works on a smaller input each time.\n\nThis is not how you'd actually sum a flat list in real Python code. `sum(prices)` is shorter, faster, and doesn't risk hitting the recursion limit. But the shape of the function is what matters here, because the same shape applies later when the data is nested and a plain loop won't work cleanly.\n\n---\n\n# Base Case and Recursive Case\n\nEvery recursive function has two parts. They're not optional, and the function won't work if either is wrong.\n\nThe **base case** is the input the function can answer without calling itself. It's where the recursion stops. For `cart_total`, the base case is the empty list. For `countdown`, the base case is `n == 0`.\n\nThe **recursive case** is everything else. It does a little bit of work, then calls the function again on a smaller piece of the input. For `cart_total`, the recursive case is \"first price plus the total of the rest\". For `countdown`, it's \"print `n`, then countdown from `n - 1`\".\n\nThe pattern always looks like this:\n\n\n```python\ndef recursive_function(input):\n if input is the simplest case:\n return the direct answer\n do a little bit of work\n return something using recursive_function(smaller_input)\n```\n\n\nIf you forget the base case, the function keeps calling itself forever. Python eventually notices and raises `RecursionError`, but only after wasting a lot of stack frames first.\n\n\n```python\ndef broken_cart_total(prices):\n return prices[0] + broken_cart_total(prices[1:])\n\nbroken_cart_total([29.99, 14.99])\n```\n\n\nThe function works fine until `prices` is empty. Then `prices[0]` raises `IndexError`, and the cascade of failed calls unwinds back through every frame. The fix is to add the base case: check `if not prices: return 0.0` before touching `prices[0]`.\n\nThe other common mistake is a recursive case that doesn't actually shrink the input. If `cart_total` called itself with the same list every time instead of `prices[1:]`, it would never reach the base case, no matter how good the base case was.\n\n\n```python\ndef stuck_cart_total(prices):\n if not prices:\n return 0.0\n return prices[0] + stuck_cart_total(prices)\n```\n\n\nThis recurses with the full `prices` list each time, so the base case is never reached. Calling it would raise `RecursionError` once Python's stack limit is exhausted. The rule is simple: the argument passed to the recursive call has to be **closer to a base case** than the original argument was. If it isn't, you have a bug.\n\n---\n\n# How the Call Stack Grows\n\nTo understand what recursion actually costs, you need to know what Python does behind the scenes for every function call.\n\nEvery time a function is called, Python creates a **stack frame**. The frame holds that call's local variables, the arguments it received, and a bookmark for where to return when the function finishes. Frames are stacked on top of each other, the most recent call on top. When a function returns, its frame is popped off the stack, and the call below it resumes where it left off.\n\nIn a regular loop, you have one frame: the function with the loop in it. The loop runs many times, but the frame doesn't grow.\n\nIn a recursive function, each call adds a new frame. If `cart_total` calls itself four times before hitting the base case, there are five frames stacked up at the deepest point: the original call plus four nested ones. Only when the base case returns can the frames start coming off the stack, one by one, each one finishing its work as it unwinds.\n\nConsider `factorial`, the textbook recursion example:\n\n\n```python\ndef factorial(n):\n if n <= 1:\n return 1\n return n * factorial(n - 1)\n\nprint(factorial(4))\n```\n\n\nHere's what happens, frame by frame, when `factorial(4)` runs.\n\n\n```mermaid\nflowchart TD\n A[\"factorial(4)
waiting on factorial(3)
result: 4 * ?\"]:::cyan\n B[\"factorial(3)
waiting on factorial(2)
result: 3 * ?\"]:::orange\n C[\"factorial(2)
waiting on factorial(1)
result: 2 * ?\"]:::teal\n D[\"factorial(1)
base case
returns 1\"]:::green\n\n A -->|\"calls\"| B\n B -->|\"calls\"| C\n C -->|\"calls\"| D\n D -.->|\"returns 1\"| C\n C -.->|\"returns 2\"| B\n B -.->|\"returns 6\"| A\n A -.->|\"final: 24\"| RESULT[\"24\"]:::red\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\nThe solid arrows on the way down are the calls. The dashed arrows on the way back up are the returns. Read top to bottom for the \"building up\" phase, then bottom to top for the \"unwinding\" phase.\n\nEach frame is paused, waiting on the frame below to return a value. `factorial(4)` can't finish its `4 * ?` until `factorial(3)` returns. `factorial(3)` can't finish its `3 * ?` until `factorial(2)` returns. And so on. Only when `factorial(1)` hits the base case and returns `1` does the whole pile start unwinding.\n\nAt its deepest point, four frames are alive at once. Each frame holds its own copy of `n` (4, 3, 2, 1, respectively). That's recursion's memory cost: one frame per level of nesting, sitting in memory until the base case lets them all collapse.\n\n\n> **INFO**\n>\n> **Cost:** Each recursive call uses a small but real amount of memory for the stack frame. A flat input of a million items, summed recursively, would need a million frames at the deepest point. That's far past Python's default limit (around 1000), which is why deep linear recursion is a bug-in-waiting and an iterative loop is the safer shape.\n\n\nYou can see the stack with a traceback any time recursion blows up:\n\n\n```python\ndef add_one_too_many(n):\n return add_one_too_many(n + 1)\n\nadd_one_too_many(0)\n```\n\n\nThe traceback shows the stack from bottom (the outermost call) to top (the deepest call). The \"Previous line repeated 996 more times\" message is Python being nice; if it printed every frame, you'd be scrolling for a while. This is what a recursion bug looks like in practice.\n\n---\n\n# Linear Recursion on Flat Data\n\nA recursive function that makes one recursive call per invocation is called **linear recursion**. It's the simplest shape, and it mirrors what a loop would do, one element at a time.\n\nThe cart-sum example from earlier was linear recursion: each call peels off one element and recurses on the rest. The same shape works for finding the maximum price, counting items, or building a new list.\n\n\n```python\ndef max_price(prices):\n if len(prices) == 1:\n return prices[0]\n rest_max = max_price(prices[1:])\n return prices[0] if prices[0] > rest_max else rest_max\n\ncart = [29.99, 14.99, 49.99, 9.99, 4.99]\nprint(max_price(cart))\n```\n\n\nThe base case is a single-element list, where the maximum is just that one element. The recursive case finds the maximum of \"everything after the first\", then compares it to the first element. The same pattern that summed the list now finds the largest entry.\n\nNotice the recursive call result is **saved into a variable** (`rest_max`) before being used. That's a useful habit because it makes the trace easier to read and prevents calling the function twice by mistake. Writing `return prices[0] if prices[0] > max_price(prices[1:]) else max_price(prices[1:])` would call `max_price(prices[1:])` twice in the worst case, doubling the work.\n\nBuilding a new list works the same way. Suppose you want to apply a 10% discount to every price:\n\n\n```python\ndef apply_discount(prices, discount=0.10):\n if not prices:\n return []\n first_discounted = prices[0] * (1 - discount)\n return [first_discounted] + apply_discount(prices[1:], discount)\n\ncart = [29.99, 14.99, 9.99]\nprint(apply_discount(cart))\n```\n\n\nThe base case returns an empty list. The recursive case puts the discounted first price at the front, and the recursively-discounted rest behind it. A list comprehension (`[p * (1 - discount) for p in prices]`) would be the natural way to do this in real code, and would be faster, but the recursive version is a clean illustration of the pattern: do one element of work, recurse on the rest, glue the results together.\n\n\n> **INFO**\n>\n> **Cost:** Linear recursion on a list of length `n` uses `n` stack frames. For `n` in the hundreds, that's fine. For `n` in the tens of thousands, you'll hit the recursion limit. Flat data is where iteration almost always wins.\n\n\nThe reason linear recursion is rarely the right choice in production Python isn't correctness, it's stack pressure. A loop processes a million items in one frame; the recursion above would need a million frames and crash long before finishing. We'll come back to this trade-off explicitly later.\n\n---\n\n# Recursion on Nested Data\n\nThe place where recursion stops being a curiosity and starts being the right tool is when the data is **tree-shaped**: each piece can contain more pieces just like itself.\n\nA category tree is a clean example. Online stores organize products into categories, and categories can contain subcategories, which can contain more subcategories, and so on. There's no fixed depth. A loop can handle the top level, but the loop body itself needs to handle the same thing one level deeper, which is exactly what recursion does.\n\nHere's a small category tree representing part of an online store, encoded as a nested dictionary. Each node has a name, a list of products in that category, and a list of subcategories.\n\n\n```python\ncatalog = {\n \"name\": \"Store\",\n \"products\": [],\n \"subcategories\": [\n {\n \"name\": \"Electronics\",\n \"products\": [\"Wireless Mouse\", \"Webcam\", \"Mechanical Keyboard\"],\n \"subcategories\": [\n {\n \"name\": \"Cables\",\n \"products\": [\"USB Cable\", \"HDMI Cable\", \"Power Strip\"],\n \"subcategories\": [],\n },\n {\n \"name\": \"Audio\",\n \"products\": [\"Headphones\", \"Earbuds\"],\n \"subcategories\": [],\n },\n ],\n },\n {\n \"name\": \"Kitchen\",\n \"products\": [\"Coffee Mug\", \"Kettle\"],\n \"subcategories\": [],\n },\n ],\n}\n```\n\n\nThe store has top-level subcategories (Electronics, Kitchen). Electronics has its own subcategories (Cables, Audio). And both Cables and Audio could in turn have their own subcategories; they happen to be empty here, but the structure allows any depth.\n\n\n```mermaid\nflowchart TD\n Store[\"Store
0 products\"]:::cyan\n Electronics[\"Electronics
3 products\"]:::orange\n Kitchen[\"Kitchen
2 products\"]:::orange\n Cables[\"Cables
3 products\"]:::teal\n Audio[\"Audio
2 products\"]:::teal\n\n Store --> Electronics\n Store --> Kitchen\n Electronics --> Cables\n Electronics --> Audio\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\nThe diagram shows the shape. Store is the root. Electronics and Kitchen sit beneath it. Cables and Audio sit beneath Electronics. The tree could be deeper, and the function we're about to write wouldn't need a single change to handle it.\n\nCounting the total products across the whole store, including nested subcategories, is a natural fit for recursion. The total for any node is \"the products at this node, plus the total of each subcategory\". That last part is the recursion: each subcategory's total is computed by the same function.\n\n\n```python\ndef total_products_in_category(node):\n direct = len(node[\"products\"])\n nested = sum(total_products_in_category(sub) for sub in node[\"subcategories\"])\n return direct + nested\n\nprint(total_products_in_category(catalog))\nprint(total_products_in_category(catalog[\"subcategories\"][0]))\n```\n\n\nThe whole store has 10 products. The Electronics subtree, which includes its own products plus Cables and Audio, has 8. The function doesn't care how deep the tree is, because each call only deals with one node and asks the same function to handle the children.\n\nThe base case here is implicit. If a node has no subcategories, `node[\"subcategories\"]` is an empty list, the `sum(...)` over it is `0`, and the function returns just `direct`. There's no `if not node[\"subcategories\"]: return ...` written out, because the empty-iteration behavior of `sum` already handles it. Recursive functions on trees often have this kind of \"soft\" base case, where the recursion stops naturally when there are no children to recurse into.\n\nThis is the shape of recursion that doesn't have a clean loop equivalent. You could rewrite it with an explicit stack and a `while` loop (we won't, in this lesson), but the recursive version reads exactly like the description of the problem.\n\nThe same pattern works for searching. Suppose you want to find which category a product lives in, and you only know the product's name.\n\n\n```python\ndef find_product_category(node, product_name):\n if product_name in node[\"products\"]:\n return node[\"name\"]\n for sub in node[\"subcategories\"]:\n result = find_product_category(sub, product_name)\n if result is not None:\n return result\n return None\n\nprint(find_product_category(catalog, \"HDMI Cable\"))\nprint(find_product_category(catalog, \"Coffee Mug\"))\nprint(find_product_category(catalog, \"Unicorn Plushie\"))\n```\n\n\nThe function first checks the current node's products. If the product is there, it returns the node's name. Otherwise it recurses into each subcategory. The first recursive call that returns a non-`None` result wins; the function returns it immediately and stops searching. If none of the subcategories find it, the function returns `None`, which the caller then treats as \"not found anywhere in this subtree\".\n\nThe key detail is that the recursive call is **inside a loop**, and the function checks each result before deciding whether to recurse further. This is sometimes called **tree recursion**, because each call can spawn multiple recursive calls instead of just one.\n\nThe product names in this example act like SKUs (the catalog's internal identifier for an item). We're using the display name directly for simplicity; in a real store you'd usually look products up by a unique ID. The shape of the recursive search wouldn't change either way.\n\n---\n\n# The Recursion Limit and Why Python Doesn't Optimize Tail Calls\n\nPython protects you from infinite recursion (and from runaway memory use) by capping how deep the call stack can grow. The default limit is around 1000 frames, and you can check it with `sys.getrecursionlimit`.\n\n\n```python\nimport sys\n\nprint(sys.getrecursionlimit())\n```\n\n\nThe exact number depends on your Python build, but 1000 is the standard default. When you exceed it, Python raises `RecursionError`. We saw the traceback earlier with `add_one_too_many`; here's another one that comes from a function that simply recurses too deep for its input:\n\n\n```python\ndef deep_countdown(n):\n if n == 0:\n return \"done\"\n return deep_countdown(n - 1)\n\ndeep_countdown(2000)\n```\n\n\nThe base case is correct (`n == 0`), and the recursive case shrinks the input correctly (`n - 1`). The function is logically fine. It just needs more frames than Python is willing to give it. Each call adds a frame, and 2000 frames is past the limit.\n\nYou can raise the limit with `sys.setrecursionlimit`, but doing so should be a deliberate choice, not a reflex:\n\n\n```python\nimport sys\n\nsys.setrecursionlimit(5000)\nprint(sys.getrecursionlimit())\n```\n\n\nThe reason this isn't a free fix is that each frame uses real memory (a few hundred bytes to a few kilobytes, depending on what's in it). Push the limit too high, and Python won't raise `RecursionError`. Instead, the operating system will run out of stack space and your process will crash with a segmentation fault, which is a much worse failure mode than a clean Python exception. Raising the limit is fine for known, bounded inputs (a category tree that you control). It's a bad idea for unbounded recursion on user data.\n\nThe next question that usually comes up is: \"Some languages optimize this away. Why doesn't Python?\"\n\nIn languages like Scheme, Scala, or Haskell, the compiler can recognize when the last thing a function does is call itself, and reuse the current stack frame instead of creating a new one. This is called **tail-call optimization** (TCO). With TCO, a tail-recursive function uses one frame total, regardless of how many times it recurses. Tail-recursive `deep_countdown(1000000)` would just work.\n\n**Python does not do this.** It's a deliberate design choice, not a missing feature. Guido van Rossum (Python's creator) has explained the reasoning more than once: tracebacks are more useful when every call leaves a frame behind, because you can see the full history of how the program got where it is. Optimizing away tail calls would collapse that history. He also pointed out that turning recursion into a loop is usually easy, so the language doesn't need to do it for you.\n\nThe practical consequence is simple: **if your recursion is deep and the recursive call is the last thing the function does, rewrite it as a loop**. Python won't optimize it for you, and the recursion limit will bite eventually.\n\nThe two `countdown` shapes side by side make the point:\n\n\n```python\ndef countdown_recursive(n):\n if n == 0:\n print(\"done\")\n return\n print(n)\n countdown_recursive(n - 1)\n\ndef countdown_iterative(n):\n while n > 0:\n print(n)\n n -= 1\n print(\"done\")\n```\n\n\nBoth produce the same output for `n = 3`. For `n = 100000`, the recursive version raises `RecursionError`, while the iterative version runs in one frame and finishes without complaint. The iterative version is what you want for any recursion that just walks forward through data; the recursive shape is reserved for problems where the structure of the data is genuinely recursive, like the category tree.\n\n---\n\n# Recursion vs Iteration\n\nThe trade-off between recursion and iteration is one of the more important judgment calls in writing readable Python code. Both can express the same computations, but each has a natural fit.\n\n\n| Use recursion when... | Use iteration when... |\n| --- | --- |\n| The data is tree-shaped or nested with no fixed depth | The data is flat (list, range, file lines) |\n| Each step naturally produces multiple sub-problems | Each step processes one element and moves on |\n| The recursive shape matches the problem's description | The problem is \"do this once per item\" |\n| Depth is bounded and small (less than a few hundred) | Depth could be large or unbounded |\n| Backtracking is involved (try, fail, undo, try again) | A simple `for` or `while` loop fits |\n\n\nThe category-tree examples earlier are the sweet spot for recursion. The tree has no fixed depth, and \"do the same thing one level deeper\" is exactly what recursion expresses. Replacing it with an iterative version means managing an explicit stack or queue, which is more code and less clear.\n\nThe cart-sum example was the opposite. A flat list has a fixed shape (one dimension), and there's no real benefit to recursion. The iterative version is shorter, faster, and immune to the recursion limit:\n\n\n```python\ndef cart_total_iterative(prices):\n total = 0.0\n for price in prices:\n total += price\n return total\n```\n\n\nSame result as the recursive version, with one frame instead of `n`, and no stack risk. For a flat list, this is the right shape.\n\nThe rule of thumb. Recursion is a tool for matching the shape of the data, not for processing it efficiently. If the data is nested, recursion will probably read more clearly than the iterative equivalent. If the data is flat, iteration will probably read more clearly and won't have the depth limitation. Pick the shape that matches the data, not the other way around.\n\nA subtle point. \"I could write this as a loop\" is true for almost any recursion (it's a theorem of computer science). The question isn't whether it's possible, it's whether it's readable. A recursive function that says \"the total of a category is the products here plus the total of each subcategory\" reads exactly like the problem description. The iterative equivalent has to introduce an explicit stack, push subcategories onto it, pop them off, and track state across iterations. Both work; one reads better.\n\n---\n\n# Memoization Preview\n\nThe last topic worth touching is what to do when a recursive function ends up doing the same work many times over.\n\nThe classic example is the Fibonacci sequence. Each number is the sum of the two before it, starting from `0` and `1`. The recursive definition is one line:\n\n\n```python\ndef fib(n):\n if n < 2:\n return n\n return fib(n - 1) + fib(n - 2)\n\nprint(fib(10))\nprint(fib(30))\n```\n\n\n`fib(10)` runs quickly. `fib(30)` takes a noticeable moment. `fib(40)` would take many seconds. `fib(50)` would feel like the program had hung. The problem isn't the recursion itself; it's that the function recomputes the same values an enormous number of times. `fib(30)` calls `fib(28)` and `fib(29)`, and `fib(29)` also calls `fib(28)`. So `fib(28)` is computed twice. And `fib(28)` calls `fib(26)` twice, each of which calls `fib(24)` twice, and so on. The number of repeated calls grows roughly like `2^n`.\n\nThe fix is **memoization**: cache each result the first time it's computed, and return the cached value on subsequent calls with the same input. Python's standard library has a one-line tool for this: `functools.lru_cache`.\n\n\n```python\nfrom functools import lru_cache\n\n@lru_cache(maxsize=None)\ndef fib(n):\n if n < 2:\n return n\n return fib(n - 1) + fib(n - 2)\n\nprint(fib(50))\nprint(fib(100))\n```\n\n\n`fib(100)` returns instantly. The `@lru_cache(maxsize=None)` line above the function is a **decorator**. For now, the only thing to know is that `@lru_cache` makes the function remember its previous answers, so a call to `fib(n)` with the same `n` returns from the cache instead of recomputing.\n\n\n> **INFO**\n>\n> **Cost:** Caching trades memory for speed. `lru_cache(maxsize=None)` remembers every result forever, which is fine for small input ranges (like `fib` with `n` up to a few thousand) but is a memory leak for unbounded inputs. Use a finite `maxsize` if the input space is large.\n\n\nMemoization is the standard cure for recursive functions that solve the same sub-problem more than once. It doesn't help recursions like `cart_total` or `total_products_in_category`, where each call has a unique input that's never visited again. It shines on overlapping recursions like `fib`, or on tree searches where the same subtree might be reached through different paths.\n\nWe won't cover decorators (or `lru_cache`'s knobs) in detail here. The point is to know that the option exists, and to recognize the symptom when you see it: a recursive function that's correct but slow, with calls that visit the same arguments many times over.","pageType":"python"}

Recursion

Get Premium