Learn

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 0 and 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)]

Finally, 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(2) and 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?

Instructions

1.

Define our 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
2.

Now take care of the recursive step.

This step involves summing two recursive calls to fibonacci().

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.

3.

Add print statements within fibonacci() to explore the different recursive calls.

Set fibonacci_runtime to the appropriate big O runtime.

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?