Recursion and Trees
Recursion, properly
No problems in this lesson. It exists because everything after it, and both of the hardest units later, assume it.
Why this lesson exists
If you already write recursion comfortably, this will take ten minutes and the drills will still be worth doing. If you do not, this is the most important lesson in the course, because backtracking and dynamic programming are both recursion with extra bookkeeping, and neither is learnable while recursion itself is shaky.
Key idea
Two parts, and only two
A recursive function needs a base case, which answers the smallest input directly, and a recursive case, which reduces a larger input to smaller ones and combines their answers.
That is the whole structure. Most difficulty comes from trying to hold the entire chain of calls in your head, which is neither necessary nor possible past about three levels.
Why it works
The leap of faith
Here is the mental move that makes recursion writable. When writing the recursive case, assume the function already works on the smaller input. Do not trace it. Do not verify it. Assume it.
In the code above, the moment you write total(values, index + 1), assume it correctly returns the sum of everything from that point on. Then your only job is to add the current element. That is one line of thinking rather than an unbounded chain.
This is not hand waving. If the base case is right, and each recursive case is right given that assumption, then the whole thing is right by induction. That is a proof, and it is why the assumption is safe.
Key idea
The three questions
Ask these in order and recursion stops being mysterious.
Does the base case return the right thing? Check it directly on the smallest input, usually empty or a single element.
Does every recursive call get a strictly smaller input? If not, it never terminates.
Given correct answers from the calls, is the combination right? This is the only step that needs thought, and it is one line.
What actually happens
Each call gets its own copy of the local variables, stacked on top of the caller's. When a call returns, its frame is discarded and the caller resumes exactly where it left off.
The depth of that stack is the space cost of a recursion, which is why an O(n) recursion can use O(n) space even when it allocates nothing. Python stops you at a depth around a thousand by default, which is a real constraint on some problems and never an issue on balanced trees.
Gotcha
Forgetting to return the recursive call
The single most common recursion bug in any language: making the call but not returning what it produced. The function runs, does all the work, throws it away, and returns None.
It is invisible in the code because the recursive line looks busy. If a recursion returns None when it should return a value, check that every path has a return in front of the call.
Tip
Two shapes worth recognizing
Linear recursion makes one call per level, so the stack is as deep as the input is long. Summing a list is this shape.
Branching recursion makes several calls per level, so the number of calls grows multiplicatively while the depth stays proportional to how far you can subdivide. Tree recursion is this shape, and so is everything in U10.
The distinction matters because the depth determines the space and the total number of calls determines the time, and for branching recursion those two are very different numbers.
Predict the output: before or after the call
The same recursion prints in two different places. Type both lines of output, each as digits separated by single spaces.
Recursion drills
Four small recursions, no trees yet. Write each one recursively even where a loop would be shorter, because the point is the shape. count_down builds a list from n to 1. sum_digits adds the digits of a non-negative integer. is_palindrome checks a string. flatten turns a nested list of lists into a flat list.
Tests
print(count_down(4), count_down(0))
print(sum_digits(1234), sum_digits(0))
print(is_palindrome("racecar"), is_palindrome("abca"), is_palindrome(""))
print(flatten([1, [2, [3, 4]], 5]), flatten([]))Output
Run the tests when you are ready.