The previous lesson ended with two debts: binary search had a "more elegant" version we could not write, and mergesort needed to sort two halves which are, in turn, lists waiting to be sorted. Both ask for the same thing, and it is what you will learn here: a function that calls itself.

Recursion is disconcerting the first time because it looks like a circular trick, and it is not: it is a different way of breaking problems down, complementary to the decomposition into functions from 04-04. Instead of splitting the problem into different subproblems, you split it into smaller versions of the same problem until you reach a case so simple it solves itself without thinking. In this lesson you will understand it, trace it, discover why in Python it is worth being suspicious of it, and use it in the three places where it wins hands down.

1. The idea: boxes inside boxes
2. The two mandatory pieces
3. The call stack and the RecursionError
4. Progressive examples with their traces
5. The call tree: factorial and Fibonacci
6. Recursion versus iteration
7. The hidden cost of naive recursion
8. Memoisation: remembering what is already computed
9. Where recursion really does win
10. Recursive binary search and merge sort
11. EasyTask v0.14: days of a nested breakdown
12. Common mistakes and tips
13. Exercises
14. Conclusion

Imagine that in Alba Studio's storeroom you are asked to count how many sheets of paper there are, and the storeroom contains boxes, some of which contain more boxes. You do not need a different procedure for each depth level. You need one single rule:

To count the sheets in a box: if it only contains sheets, count them. If it contains other boxes, count the sheets in each one and add up the results.

Notice what you have just done: you have defined "counting the sheets in a box" in terms of itself, applied to something smaller. And it works because the boxes are not infinite: sooner or later you reach one that only contains sheets and there you stop. The same happens with Russian dolls, with folders inside folders on your hard disk, or with the definition of "ancestor": your parents, and your parents' ancestors. That is all recursion is: a recursive function calls itself with a smaller version of the problem, trusting that the call will hand back the right answer.

Every recursive function has exactly two parts, and neither of them may be missing:

When writing a recursive function, always ask yourself the three questions in this order: what is the simplest case I can solve without thinking? (that is the base one), how do I shrink the problem towards that case? (that is the recursive call) and what do I do with what comes back? (that is this level's work). And there is a requirement beyond having the two pieces: the recursive case must get closer to the base one. countdown(n - 1) gets closer to zero; countdown(n) gets closer to nothing and hangs just as if there were no base case.

In 04-01 you saw that when a function calls another, the first one waits for the second to finish. Python stores every pending call in the call stack, with its variables and the exact point to return to. Recursion stacks calls of the same function:

The stack grows down to the base case and then unwinds in reverse order. That has a first-order practical consequence: every pending call takes up memory. Python limits the depth to about 1,000 calls and, if that is exceeded, aborts with RecursionError: maximum recursion depth exceeded.

That RecursionError is, in fact, good news: Python warns you about a logic flaw —the base case is missing or you are not getting closer to it— before exhausting the memory. Raising the limit is possible, but it is nearly always the wrong answer: if your recursion needs more than a thousand levels, what you need is a loop.

Factorial. The factorial of n is the product of the integers from 1 to n, and its mathematical definition is already recursive: n! = n × (n-1)!, with 0! = 1.

Trace of factorial(4); the first columns are the way down, stacking calls, and the last one is the way back, when each level receives its result and multiplies it:

Read the last column from the bottom up and you will see how the result is built: 1, 2, 6, 24. Nothing is computed on the way down; all the real work happens on the way back. The same scheme works over collections: the sum of a list is its first element plus the sum of the rest, and a reversed string is the rest reversed plus its first character.

values[1:] is the slice from 05-01: "all but the first". Every call receives a collection one element shorter, so it gets closer to the base case. With [3, 5, 2] you get 3 + (5 + (2 + 0)), that is, 10; and with "Alba", reverse("lba") + "A" → ("ab" + "l") + "A" → "ablA". In production you would write sum(values) and text[::-1]; this is to see the mechanics.

Factorial generates a chain of calls: each level calls just once. Fibonacci —each number is the sum of the two before it, starting from 0 and 1— generates a tree, because each level calls twice:

Look at the marked nodes: fib(3) is computed twice and fib(2) three times, with its whole subtree repeated every time. And that is only with n = 5. The difference between the two shapes is total: factorial makes n calls, Fibonacci makes roughly twice as many for every unit n goes up. That explosion is the subject of section 7.

Everything that can be written with recursion can be written with a loop, and the other way round. The choice is about clarity and cost, not about possibility.

The iterative factorial fits in four lines —result = 1, a for i in range(2, n + 1) doing result *= i, and a return— and it is faster than the recursive one. The practical rule in Python is simple and worth taking seriously: prefer to iterate, unless the problem is naturally recursive. And it is when its data is tree-shaped —folders inside folders, dictionaries inside dictionaries, subtasks inside tasks— or when the algorithm splits the problem into chunks that are solved the same way, like mergesort. For sweeping, counting or accumulating, the loop always wins. Other languages (Scheme, Haskell, Erlang) optimise a certain kind of recursion so it consumes no stack, with a technique called tail call optimization; Python does not, deliberately, and that is one more reason to be suspicious of deep recursion here.

The fibonacci from section 5 is correct and it is a disaster. Let us measure it with time.perf_counter(), as in 06-02, wrapping the call between two clock readings and subtracting them:

Every five units of n the time is multiplied by ten, and fib(50) would take over an hour to compute a number that fits on one line. The reason is in the tree from section 5: the algorithm recomputes over and over what it had already computed; for fib(35) it computes fib(10) tens of thousands of times, always getting the same thing. Careful, then: the problem is not recursion, it is the repeated work, and the fix is not to remove the recursion but to stop repeating.

Memoising means storing the result of every computation in a dictionary so as not to repeat it. It is the time-memory trade-off from 06-01 in its purest form: we spend memory so as not to spend time.

The dictionary is the perfect structure for this because of what you learned in 06-01: checking n in memo is practically instantaneous thanks to the hash table. And notice the memo=None: never use an empty dictionary or list as a parameter's default value, because Python creates them just once, when the function is defined, and they would be shared across every call. The effect is spectacular: fibonacci_memo(35) goes from 4 seconds to under a ten-thousandth, because each fib(k) is computed just once and the tree turns into a chain. Python ships this ready-made in a standard library decorator:

That line starting with @ is a decorator: an annotation that wraps the function and adds behaviour to it —here, the memory of results— without touching its code. We will not study them in this course; take away that @lru_cache is the professional way to memoise, that fast_fibonacci.cache_info() reports its hits, and that it only works if the arguments are immutable (numbers, strings, tuples), because it uses them as dictionary keys.

So far recursion has come out as a pretty, slower version of the loop. That changes completely when the data is tree-shaped, because then a loop is not enough: you would need as many nested loops as there are levels, and you do not know how many there are. Let us pick up the dictionary of dictionaries from 05-04, now with unknown depth:

The base case is "this does not contain anything else inside"; the recursive case is "for each thing inside, repeat". The level parameter does not drive the recursion, it only keeps track of the indentation: passing information downwards is a common pattern. And isinstance(x, dict) is essential because we do not know what we are going to meet at each level. The same scheme walks disk folders; pathlib (05-05) already provides the recursive walk with rglob, but writing it teaches the structure:

Here recursion is not an aesthetic choice: it is the only reasonable way to do it, because nobody knows how many folder levels there are. And the base case is not an if at the top, but the natural situation in which the folder contains no subfolders and the for calls nobody.

As promised in 06-01: binary search is naturally recursive, because "search in this chunk" is the same problem as "search in half of this chunk".

Compare it with the iterative version from 06-01 and you will see the exact translation: the while has turned into the recursive call and the exit condition left <= right into the base case left > right, inverted. The default parameters (04-02) let you call it as recursive_binary_search(codes, 170) without passing the bounds. Tracing the search for 170 in [102, 118, 134, 156, 170, 189, 203, 240]:

Which one is better? The iterative one, in Python, because it does the same without eating stack; the recursive one reads better and is the one you will see in books. And in production, neither: bisect.

As promised in 06-02, and the canonical example of divide and conquer: split the list down the middle, sort each half recursively and merge the two already sorted halves.

merge is the non-recursive piece and the most important one: it sweeps the two lists in parallel with two indices, always taking the smaller of the two fronts, in a single pass. That <= instead of < is what makes the algorithm stable: on a tie it takes the one from the left, which came first. And the last line adds whatever is left unswept in one of the two lists, which by construction is already sorted. Trace of mergesort([3, 5, 2, 4]):

The list is split down the middle until reaching one-element chunks —which are sorted by definition— and then rebuilt by merging. With 1,000 elements there are about 10 levels of splitting and each level costs one full pass: some 10,000 operations, against bubble sort's million. That is the difference you saw in the timing table in 06-02, and Timsort uses exactly this merge function to join the stretches it sorts with insertion.

Marta has started breaking the big jobs down into subtasks, and those in turn into smaller subtasks, with no fixed number of levels, and she needs to know how many days a whole project adds up to. It is the case from section 9, and it is only solved properly with recursion.

The screen output, where each branch shows its own total: Sole Bakery identity 10d, and inside it Logo 3d (with Sketches 2d and Vector artwork 1d indented below), Stationery 3d and Shop sign 4d. Three observations about this code:

• The base case is not an if. When subtasks is empty, the for never runs and the function returns task["days"] directly. It is the cleanest way to write the base case when sweeping a collection: the empty list is the base case by itself.
• The data structure and the algorithm fit together. Every node has the same shape —name, days, subtasks—, be it the root or the last leaf, and that is why the same function serves every level: designing the data with that uniformity is what makes the recursion possible. And that way neither function knows how many levels there are, which is exactly what was asked for; with nested loops you would have to fix a maximum depth up front. And careful: show_breakdown recomputes each branch's total, repeating work just like Fibonacci. With three levels it is irrelevant; if the breakdown grew, memoising would be in order.

Forgetting the base case or not getting closer to it. Both symptoms are the same RecursionError. Check that there is an if that returns without calling itself and that the argument of the recursive call is closer to that case at every step. And forgetting the return in front of the recursive call. factorial(n - 1) without return computes the result and throws it away; the function returns None and multiplying raises TypeError. In a recursive function that returns a value, nearly every branch carries a return.

Using {} or [] as a parameter's default value, typical when memoising. Python creates that object just once and shares it across every call: the results of one query contaminate the next. Use None and create it inside. And beware of recursion over lists with slices: add_up(values[1:]) copies the whole list on every call, so adding up 1,000 numbers copies half a million elements; for large collections, pass indices or use a loop.

Tip: trust the recursive call. The most common learning mistake is trying to follow every level mentally. Do not: take it as given that factorial(n - 1) returns the right factorial and limit yourself to checking the base case and the step. If both are right, the function is right. And if in doubt, draw the tree: three levels on paper are enough to see whether the problem shrinks and whether there is repeated work, like Fibonacci's. It is the desk check from 01-05 applied to recursion.

Trace add_up([4, 1, 6]), giving in a table each call, what it waits for and what it returns. Then draw the call tree of fibonacci(4) and count how many times fibonacci(2) is computed. Finally, explain what countdown(2) prints if you swap the last two lines of the function body.

Over the subtask structure from section 11, write two recursive functions: count_leaves(task), returning how many subtasks with no subtasks of their own there are in the whole branch (the leaves of the tree, that is, the real work); and longest_task(task), returning the name of the leaf with the most days in the whole branch.

Write a recursive power(base, exponent) that computes base ** exponent without using the ** operator, with this property: if the exponent is even, base^n = (base^(n/2))²; if it is odd, base^n = base × base^(n-1). Compare how many calls it makes, with exponent = 16, against the version that subtracts one from the exponent each time.

Solution 1. Trace of add_up([4, 1, 6]):

In the tree of fibonacci(4), fibonacci(2) is computed twice: once hanging off fib(3) and once directly off fib(4). And if in countdown you swap the print(n) and the recursive call, the count comes out backwards: first Done! and then 1, 2. The reason is the one from section 4: what goes before the call runs on the way down and what goes after it, on the way back.

Solution 2.

count_leaves explicitly distinguishes the leaf —worth 1— from the branch, which is worth the sum of its children. longest_task uses an important trick: it returns a tuple (name, days) instead of just the name, because comparing candidates at the level above needs the days. It is the "returning several values" of 04-02 in the service of recursion: each level returns what the level above needs in order to decide.

Solution 3.

The key is half = power(base, exponent // 2) stored in a variable: if you wrote power(...) * power(...) you would compute the same thing twice and be back to Fibonacci's problem. With exponent 16 the split is 16 → 8 → 4 → 2 → 1 → 0: five calls, against the seventeen of the version that subtracts one each time. It is the same halving idea as binary search and mergesort, applied to arithmetic; in Python, of course, you write base ** exponent.

A recursive function calls itself with a smaller version of the same problem, and it only works if it has its two pieces: a base case that returns without calling itself and a recursive case that gets closer to it. Every pending call lives in the call stack, which Python limits to about a thousand levels before raising RecursionError; raising the limit with sys.setrecursionlimit is almost never the right fix. On the way down the calls are stacked and on the way back the result is built, as the traces of the factorial, the sum of a list and the reversal of a string show. Factorial generates a chain of calls and Fibonacci a tree, and there lies the trap: naive Fibonacci repeats so much work that fib(40) takes forty-five seconds. The cure is not to abandon recursion but to stop repeating, with memoisation —a dictionary of already computed results, or the @lru_cache decorator—, which is the time-memory trade-off in its purest state. Against iteration, recursion loses on memory and speed and wins on clarity when the data is tree-shaped (nested structures, disk folders, subtask breakdowns) or when the algorithm splits the problem: the recursive binary search promised in 06-01 and the mergesort promised in 06-02, whose merge function sweeps two sorted lists in a single pass and is the very one Timsort uses. EasyTask reaches v0.14 and computes the days of a project broken down into subtasks at any depth.

With this you have all the module's pieces, and also a pile of loose claims we have been making without being able to prove them: "twenty comparisons against a million", "doubling the data quadruples the work", "the tree turns into a chain", "this is a time-memory trade-off". They all describe the same thing —how much a program costs according to the size of its data— and they all call for precise vocabulary. In Efficiency and Big-O Notation you will finally have it, and with it you will be able to look at any function and say out loud how much it is going to cost before running it.