Jared NielsenIf you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the recursive Fibonacci sequence in JavaScript and Python.
This article originally published at jarednielsen.com
How to Code the Recursive Fibonacci Algorithm
Programming is problem solving. There are four steps we need to take to solve any programming problem:
Understand the problem
Make a plan
Execute the plan
Evaluate the plan
Understand the Problem
To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:
GIVEN a number, _n_
WHEN I call a recursive Fibonacci function
THEN I am returned the _nth_ member of the Fibonaccis sequence
That’s our general outline. We know our input conditions, an integer n, and our output requirements, the nth member of the Fibonacci sequence, and our goal is to calculate this recursively.
Let’s make a plan!
Make a Plan
Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:
Decomposition
Pattern recognition
Abstraction
Algorithm design
The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?
0
If n is equal to 0, what is the equivalent Fibonacci number?
0
Let's map out the first 10 numbers so we're clear on the goal.
| n | nth |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
Let's pseudo/hardcode 0:
FUNCTION fibonacci
INPUT n
IF n IS EQUAL TO 0
RETURN n
What's the next smallest problem?
1
If we refer to our table above, we see that the result of n = 1 will return 1. We can simply add this to our conditional:
FUNCTION fibonacci
INPUT n
IF n IS EQUAL TO 0 OR n IS EQUAL TO 1
RETURN n
Hey! Look at that. We just establisehd our base case. Now we need to define our recursive case.
Let's look at the next smallest problem, 2.
If our input is 2, what do we expect the return value to be?
1
How do we arrive at 1 in the Fibonacci sequence? It's the sum of the two preceding numbers, 0 and 1.
If our input is 3, what do we expect the return value to be?
2
How do we arrive at 2 in the Fibonacci sequence? It's the sum of the two preceding numbers, 1 and 1.
If our input is 4, what do we expect the return value to be?
3
In order to return a value of 3 when n is equal to 4, we know we need to add 1 and 2, the numbers that precede 3 in the Fibonacci sequence.
Do you see a pattern?
You might be tempated to say that it's simply n - 1, but what if our input is 5? What do we expect the return value to be?
Not 4.
It's 5!
In order to return a value of 5 when n is equal to 5, we know we need to add 2 and 3, the numbers that precede 5 in the Fibonacci sequence.
If we call our Fibonacci function f() for short, we know that:
f(5) = 3 + 2
And...
f(4) = 2 + 1
And...
f(3) = 1 + 1
And...
f(2) = 1 + 0
And f(1) is our base case because there aren't two preceding numbers to add to arrive at this value.
Do you see the pattern?
f(5) = f(4) + f(3)
And...
f(4) = f(3) + f(2)
And...
f(3) = f(2) + f(1)
In other words...
f(5) = (f(3) + f(2)) + (f(2) + f(1))
And so on...
Now we can make the leap to abstraction: the recursive Fibonacci, or f() of n can be expressed as f(n - 1) + f(n - 2). We can translate this to pseudocode:
FUNCTION fibonacci
INPUT n
IF n IS EQUAL TO 0 OR n IS EQUAL TO 1
RETURN n
RETURN fibonacci(n - 1) + fibonacci(n - 2)
Execute the Plan
Now it's simply a matter of translating our pseudocode into the syntax of our programming language.
How to Code the Recursive Fibonacci Algorithm in JavaScript
Let's start with JavaScript...
const fibonaive = n => {
if (n == 0 || n == 1) {
return n;
}
return fibonaive(n - 1) + fibonaive(n - 2);
};
How to Code the Recursive Fibonacci Algorithm in Python
Now let's see it in Python...
def fibonaive(n):
if (n ==0) or (n == 1):
return n
return fibonaive(n - 1) + fibonaive(n - 2)
Evaluate the Plan
Can we do better?
We sure can!
Our solution above is referred to as a "naive" implementation of Fibonacci.
Why is it naive? Because the runtime is really bad.
What is the Big O Of Recursive Fibonacci Sequence?
It’s O(2^n).
(Actually, it’s O(1.6^n), but who’s counting?)
If you want to learn how to calculate time and space complexity, pick up your copy of The Little Book of Big O
Take a look at this diagram of our recursive call branches.
Why is this algorithm inefficient?
Overlapping subproblems! We solve the same problems repeatedly in our branches.
How many times do we solve f(0)?
How many times do we solve f(1)?
How many times do we solve f(2)?
How many times do we solve f(3)?
The answer to all of the above is: too many!
What's the solution?
Dynamic programming!
If you want to learn more, check out my article What is Dynamic Programming? Memoization and Tabulation
A is for Algorithms
Give yourself an A. Grab your copy of A is for Algorithms
