How to Code the Recursive Fibonacci Algorithm

If 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:

1. Understand the problem

2. Make a plan

3. Execute the plan

4. 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.

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