Recursion with Fibonacci and Python
What is Recursion?
Recursion means “defining a problem in terms of itself”. Let’s say we have a very large or complex problem to solve. If we can break this problem down into smaller versions of itself, we may be able to find a way to solve one of these smaller versions and then be able to build up to a solution to the entire problem. This is the idea behind recursion; recursive algorithms break down a problem into smaller pieces which you either already know the answer to, or can solve by applying the same algorithm to each piece, and then combining the results.
In order to better understand recursion, let’s look at the following problem: Fibonacci in Python
A Fibonacci sequence is defined as follows: the first and second terms in the sequence are 0 and 1. Subsequent terms are found by adding the preceding two terms in the sequence. Write a program to generate the first n terms of the sequence.
Let’s start by thinking through a couple of example test cases.
If we have a function called fib that takes in argument n:
When we call fib(0), the expected output is 0.
When we call fib(1), the expected output is 1.
When we call fib(2), the expected output is 1.
When we call fib(3), the expected output is 2.
And so on.
We need two things when writing a recursive function: The Base Case and the Recursion Call.
Base Case:
A base case in recursion is the condition based on which the recursion ends, and the stack starts to unwind, or return values. If we don’t give a stopping point, our function will never stop calling itself, causing an infinite recursion. We don’t want this!
In order to find the base case, ask yourself, what is the simplest possible input for the function. Or, what is the point that we want our function to stop?
Let’s think about the base case for this problem. As we already determined:
When we call fib(0), the expected output is 0.
When we call fib(1), the expected output is 1.
When we call fib(2), the expected output is 1.
So, we could say that if n == 0, return n. And if n == 1, return n. This is our base case, more simply written:
if n < 2, return n
Recursion Call:
If n is 2 or greater, we go into our recursive call, which is to return the sum of the previous two numbers:
return fib(n-1) + fib(n-2)
Let’s put it all together:
def fib(n):
# Base Case
if n < 2:
return n
else:
# Recursive Call
# return the sum of the previous two terms
return (fib(n - 1) + fib(n - 2))Let’s call this function and review what is happening at each step.
If we call fib(4), 4 is not less than 2, so we bypass the if statement and go immediately into the recursive call, which gives us:
fib(4–1) = fib(3)
+
fib(4–2) = fib(2)
Now we start again on the left with fib(3). Here we have n = 3 which is not less than 2, so we go to the recursive call again, getting fib(3–1) = fib(2) and fib(3–2) = fib(1).
We continue with the right, fib(2) give us fib(1) and fib(0).
Again on the left, fib(2) give us fib(1) and fib(0).
This is where it starts to get interesting. We now reach fib(1). Remember our base case:
if n < 2:
return n
So, fib(1) is evaluated to 1
Same with the next fib(1) = 1
And fib(0) = 0
We continue on the left, fib(1) = 1
And fib(0) = 0
Now we start adding the values together. Remember our recursive call:
return (fib(n - 1) + fib(n - 2))So we add 1 + 0 = 1
We then add 1 + 1 = 2
On the right, 1 + 0 = 1
Finally, we have the last two values, 2 + 1 = 3. This completes our calculation: fib(4) = 3.
