Many, many function calls.
We've now seen what standard recursion looks like — a function that calls itself. We'll now make our lives slightly more complicated by introducing tree recursion — a function that calls itself not once but multiple times.
A classic example of tree recursion is a Fibonacci Sequence. In this sequence, a given number is the sum of the previous two numbers. The sequence goes as follows:
Let's write this in code!
Accepts any value greater than or equal to 1 and returns that term in the
if n == 0 or n == 1:
return fib(n-1) + fib(n-2)
An important observation here: Why do we have
n==0as a base case, even when that is not acceptable as an input. It's because while the user might never give us
nas the value for
n, our recursive calls might. Consider the case
fib(2)— which makes the recursive calls
fib(0)— 1 + 0 — 1, as required!
We could have written something like
n==1 or n==2as our base case as well, but using this structure instead allows us to introduce the idea of base cases for inputs invalid for the user but valid for the recursive calls.
Regardless, something like
fib(4)looks like the following in terms of recursive calls:
= fib(3) + fib(2)
= (fib(2) + fib(1)) + (fib(1) + fib(0))
= ((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))
= ((1 + 0) + 1) + (1 + 0)
= (1 + 1) + 1
It is easier to visualize by representing function calls as nodes in a tree:
Recursive Tree for fib(4)
As you can see, this looks like an upside down tree (kinda... I wouldn't think too hard about it, most computer scientists don't go outside very often). The big idea here is that, at every stage, we make two recursive calls and then combine them in some way. This is tree recursion!