DEV Community

Khalil Saboor
Khalil Saboor

Posted on

Fibonacci: Recursion vs Iteration

Alt:

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
Enter fullscreen mode Exit fullscreen mode

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);
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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)

Collapse
 
misterpoloy profile image
Juan P. Ortiz

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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
risingh1981 profile image
risingh1981

Minor error: You are using 0 for the first Fib #, but F(0) = 0 and F(1) = 1

Collapse
 
ashrav profile image
ashrav

"i" should start with 1, or it should continue till <= n;

Collapse
 
awwsmm profile image
Andrew (he/him)

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.

Collapse
 
edh_developer profile image
edh_developer

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.

Collapse
 
adipginting profile image
Adi Primanda Ginting • Edited

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

Collapse
 
wozaisuzhou profile image
Danny

there is another simple way , just need 2 lines code ,

please reference to here : dev.to/wozaisuzhou/algorithms-chal...