How to Code the Recursive Fibonacci Algorithm
Tags: algorithms, javascript, python, beginners
Published: 2023-05-19 13:13:19

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](https://jarednielsen.com/algorithm-recursive-fibonacci/)_


## How to Code the Recursive Fibonacci Algorithm 

[Programming is problem solving](https://jarednielsen.com/programming-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:

```md
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...
```js
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...
```py
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](https://gum.co/big-o)

Take a look at this diagram of our recursive call branches.

![Tree diagram of recursive calls to a Fibonacci function](./jarednielsen-recursive-fibonacci-tree.png)

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](https://jarednielsen.com/dynamic-programming-memoization-tabulation/)


## A is for Algorithms

![A is for Algorithms](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j1ia6trvz5lm0978583x.png)
Give yourself an A. Grab your copy of [A is for Algorithms](https://gum.co/algorithms)