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.

A 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.

Counting down from a number is the simplest example that shows the shape without doing real work:

The 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.

That's the whole pattern. Two questions to ask of any recursive function:

If 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.

A 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.

A 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():

The 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.

This 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.

Every recursive function has two parts. They're not optional, and the function won't work if either is wrong.

The 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.

The 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".

The pattern always looks like this:

If 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.

The 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].

The 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.

This 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.

To understand what recursion actually costs, you need to know what Python does behind the scenes for every function call.

Every 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.

In 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.

In 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.

Consider factorial, the textbook recursion example:

Here's what happens, frame by frame, when factorial(4) runs.

The 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.

Each 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.

At 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.

You can see the stack with a traceback any time recursion blows up:

The 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.

A 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.

The 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.

The 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.

Notice 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.

Building a new list works the same way. Suppose you want to apply a 10% discount to every price:

The 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.

The 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.

The 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.

A 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.

Here'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.

The 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.

The 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.

Counting 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.

The 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.

The 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.

This 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.

The same pattern works for searching. Suppose you want to find which category a product lives in, and you only know the product's name.

The 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".

The 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.

The 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.

Python 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.

The 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:

The 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.

You can raise the limit with sys.setrecursionlimit, but doing so should be a deliberate choice, not a reflex:

The 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.

The next question that usually comes up is: "Some languages optimize this away. Why doesn't Python?"

In 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.

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.

The 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.

The two countdown shapes side by side make the point:

Both 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.

The 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.

The 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.

The 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:

Same result as the recursive version, with one frame instead of n, and no stack risk. For a flat list, this is the right shape.

The 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.

A 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.

The last topic worth touching is what to do when a recursive function ends up doing the same work many times over.

The 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:

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.

The 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.

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.

Memoization 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.

We 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.