More handy tools
INPUT · Slides
01 / 07
Think about the factorial of 5 — everything from 1 to 5 multiplied together.
That is 5 * 4 * 3 * 2 * 1. There is another way to look at it, though.
"The factorial of 5 is 5 times the factorial of 4."
The same statement, and yet "factorial" has turned up again on the right-hand side. The big problem has become a slightly smaller problem of the same shape.
Writing that view down as it stands is recursion.
02 / 07
Inside a function, call the function itself. That is all recursion is.
Read it like this.
n is 0 the answer is 1 (the starting point for multiplying)n times "the factorial of n - 1"Seeing factorial turn up inside factorial may feel uncomfortable. Python does not mind — all it asks is that the body exists by the time the call happens.
def factorial(n): if n == 0: return 1 return n * factorial(n - 1)print(factorial(5))Result
120
03 / 07
This is the part that matters most. You must always provide a case where it does not call itself. That case is called the base case.
In the example above it is if n == 0: return 1. Arrive there and it finishes without calling itself again.
Leave it out and it calls itself for ever, until Python steps in and stops it.
def factorial(n): return n * factorial(n - 1)factorial(5)Run that and you get RecursionError: maximum recursion depth exceeded, which means "the depth of calling itself has gone past the limit".
When you write recursion, write the base case first. Make a habit of it.
04 / 07
Recursion is hard to follow in your head, which is where the print debugging from Chapter 4 earns its keep.
Show "what n was when this call came in" at the top of the function. You should see it getting smaller and stopping at 0.
Once it has come down to 0, the answer gets built back up the other way: 1, then 1, then 2, then 6.
def factorial(n): print(f"factorial({n})") if n == 0: return 1 return n * factorial(n - 1)print(factorial(3))Result
factorial(3) factorial(2) factorial(1) factorial(0) 6
05 / 07
To be honest, both the factorial and the total read better written with for. The total of the list below would be far plainer as a loop that adds things up.
You learn recursion anyway, because some problems can only be written this way.
There is a weakness, too. Every call means Python has to remember how far it has got, so going deep eats memory. In Python you run out at a little over a thousand.
Reach for for first, and use recursion when for will not do. That order will serve you.
def total(numbers): if len(numbers) == 0: return 0 return numbers[0] + total(numbers[1:])print(total([1, 2, 3, 4]))Result
10
06 / 07
Calling yourself once is not the only option. The Fibonacci sequence is the run of numbers where each one is the previous two added together.
0, 1, 1, 2, 3, 5, 8, 13, ...
"The nth is the sum of the n-1th and the n-2th." Write that down as it stands and you have recursion. The base case is "anything smaller than 2 stands as it is".
This is an example where recursion is what makes it short. With for you need variables holding the previous two, and it gets fiddly.
def fibo(n): if n < 2: return n return fibo(n - 1) + fibo(n - 2)print(fibo(10))Result
55
07 / 07
Recursion shines brightest on data that has the same sort of thing inside it.
Folders inside folders, replies to replies, lists inside lists. A for loop cannot get all the way round this kind of nested structure, because the depth is not fixed. Two levels means two loops, three means three — there is no writing your way out of that.
The flatten below takes a nested list and makes it flat. If an item is a list it calls itself to unpack it; otherwise it adds the item as it is. That alone copes with any number of levels.
You do not have to care how deep it goes — that is why recursion is worth the trouble of learning.
def flatten(xs): result = [] for x in xs: if type(x) == list: result += flatten(x) else: result.append(x) return resultprint(flatten([1, [2, [3, 4]], 5]))Result
[1, 2, 3, 4, 5]