🎄Tree Recursion

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:

$$1, 1, 2, 3, 5, 8, 13, 21, 35, 56...$$

Let's write this in code!

def fib(n):
    '''
    Accepts any value greater than or equal to 1 and returns that term in the 
    fibonacci sequence.
    '''
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

An important observation here: Why do we have n==0 as a base case, even when that is not acceptable as an input. It's because while the user might never give us n as the value for n, our recursive calls might. Consider the case fib(2) — which makes the recursive calls fib(1) and fib(0)  — 1 + 0 — 1, as required!

We could have written something like n==1 or n==2 as 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(4)
= 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
= 3

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!