Fibonacci: Recursion vs Iteration

#java #beginners #algorithms #codenewbie

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

For more information on Dynamic programming approach

Top comments (7)

Juan P. Ortiz • Apr 25 '20

Your iterative solution is wrong, does not work for any number.
onlinegdb.com/HyqiFsZY8

In this case, we manually handle cases for 1 and 2 and start the loop from 2:

int getNthFib(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    int prevPrev = 0;
    int prev = 1;
    int currentNumber;
    for (int i = 2; i < n; i++) {
        currentNumber = prevPrev + prev;
        prevPrev = prev;
        prev = currentNumber;
    } 
    return currentNumber;
}