DEV Community

Fibonacci: Recursion vs Iteration

Khalil Saboor on November 08, 2018

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