# Fibonacci: Recursion vs Iteration

### Khalil Saboor ・3 min read

A common whiteboard problem that I have been asked to solve couple times, has been to **"write a function to generate the nth Fibonacci number starting from 0,1"**. In this post, however, I want to address a common follow up question for this problem and that is what method is more efficient for solving this problem Recursion or Iteration.

# NOTE

It best practice to always attempt this problem before reading further into the article. So I listed out a few common tools for completing this problem.

- Pen/Marker
- Notebook/WhiteBoard
- VS Code
- The Internet

The Fibonacci numbers are a sequence of integers in

which the first two elements are 0 & 1, and each following

elements are the sum of the two preceding elements:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ..., 233

# The Problem

*Write a function to generate the nth Fibonacci number.
The nth Fibonacci number is given by:*

```
Fn = Fn-1 + Fn-2
The first two terms of the series are 0, 1.
For example: fib(0) = 0, fib(1) = 1, fib(2) = 1
```

# Solution #1 Using Recursion

```
public static int fibonacciRecursion(int nthNumber) {
//use recursion
if (nthNumber == 0) {
return 0;
} else if (nthNumber == 1) {
return 1;
}
return fibonacciRecursion(nthNumber - 1) + fibonacciRecursion(nthNumber - 2);
}
```

# Analysis

By using Recursion to solve this problem we get a cleanly written function, that checks. If the given number is equal to 0 and 1 we return both given numbers.

If we pass a number that is greater than 0 and 1. Then we make two recursive calls where we add both calls with the nthNumber minus 1 and 2 in both calls.

Passing these Integers 0, 1, 2, 3, 4, 5, Will most likely give us --> 0, 1, 1, 2, 3, 5 in a timely fashion.

But what happens if we pass higher numbers like 50, 67, 100. Well if you try to run the function with the given numbers in you're IDE. You will begin to notice how much longer it takes for this method gives us our Fibonacci number. Now trying to run a Space Complexity analysis will be a tricky thing to do because of a lot of things are happening behind the scenes of this recursive function. The reason for the poor performance is heavy push-pop of the stack memory in each recursive call.

Now for a way around this would be using memorization and storing each Fibonacci calculated so. But for now, I'm going to move along to the Iteration method and why it would compute our 100th Fibonacci number faster.

# Solution #2 Using Iteration

```
public static int fibonacciLoop(int nthNumber) {
//use loop
int previouspreviousNumber, previousNumber = 0, currentNumber = 1;
for (int i = 1; i < nthNumber ; i++) {
previouspreviousNumber = previousNumber;
previousNumber = currentNumber;
currentNumber = previouspreviousNumber + previousNumber;
}
return currentNumber;
}
```

# Analysis

The Iteration method would be the prefer and faster approach to solving our problem because we are storing the first two of our Fibonacci numbers in two variables (previouspreviousNumber, previousNumber) and using "CurrentNumber" to store our Fibonacci number. Storing these values prevent us from constantly using memory space in the Stack. Thus giving us a time complexity of O(n).

For more information on Stack and Heap memory in the context of Java

The best way to solve this is to point out the relationship between the nth Fibonacci number and the golden ratio. Saves a lot of calculations.

It's also a good opportunity to talk about tail recursion, particularly with regards to Java being a language that doesn't do tail call optimization.

There is a fibonacci algorithm that its O(n) is log(n). Would be good if you cover it?