So far our recursive functions have all included a single recursive call within the function definition.
Let’s explore a problem which pushes us to use multiple recursive calls within the function definition.
Fibonacci numbers are integers which follow a specific sequence: the next Fibonacci number is the sum of the previous two Fibonacci numbers.
We have a self-referential definition which means this problem is a great candidate for a recursive solution!
We’ll start by considering the base case. The Fibonacci Sequence starts with
1 respectively. If our function receives an input in that range, we don’t need to do any work.
If we receive an input greater than
1, things get a bit trickier. This recursive step requires two previous Fibonacci numbers to calculate the current Fibonacci number.
That means we need two recursive calls in our recursive step. Expressed in code:
fibonacci(3) == fibonacci(1) + fibonacci(2)
Let’s walk through how the recursive calls will accumulate in the call stack:
call_stack =  fibonacci(3) call_stack = [fibonacci(3)]
To calculate the 3rd Fibonacci number we need the previous two Fibonacci numbers. We start with the previous Fibonacci number.
fibbonacci(2) call_stack = [fibbonacci(3), fibbonacci(2)]
fibonacci(2) is a base case, the value of
1 is returned…
call_stack = [fibbonacci(3)]
The return value of
fibonacci(2) is stored within the execution context of
fibonacci(3) while ANOTHER recursive call is made to retrieve the second most previous Fibonacci number…
fibonacci(1) call_stack = [fibonacci(3), fibonacci(1)]
fibonacci(1) resolves because it meets the base case and the value of
1 is returned.
call_stack = [fibonacci(3)]
The return values of
fibonacci(1) are contained within the execution context of
fibonacci(3), which can now return the sum of the previous two Fibonacci numbers.
As you can see, those recursive calls add up fast when we have multiple recursive invocations within a function definition!
Can you reason out the big O runtime of this Fibonacci function?
fibonacci() function that takes
n as an argument.
Let’s address our base cases:
- if the input is 1, we return 1
- if the input is 0, we return 0
Now take care of the recursive step.
This step involves summing two recursive calls to
We need to retrieve the second to last and last Fibonacci values and return their sum.
We can get the second to last Fibonacci by decrementing the input by 2 and the last by decrementing the input by 1.
Add print statements within
fibonacci() to explore the different recursive calls.
fibonacci_runtime to the appropriate big O runtime.