best way to find Fibonacci number

Question

Fibonacci series is 0 1 1 2 3 5 8... and so on. It can be obtained using swapping elements and displaying them whereas we can obtain it using array. I was asked to find it using recursion in interview and main logic for it,

int fib(int n){
if(n<1)
    return 1;
else
    return fib(n-1)+fib(n-2);}

It generate problem for stack for big number because we are increasing complexity here. So what is optimum way here?

@LuisMuñoz this code is method in my java program. What is invalid in that method with respect to java? — Rajesh Navagare, Mar 08 '17 at 16:35
A standard way to make your code feasible to run for larger numbers is to use memoization (https://en.wikipedia.org/wiki/Memoization) which is easy enough to implement in Java. But -- Fibonacci numbers grow very big very fast, so you will rapidly run into problems with what an `int` can hold, so you should probably switch to big integers. Another idea, is to let a recursive helper function return *pairs* of two successive Fibonacci numbers -- this will eliminate the double recursion which is the main problem. — John Coleman, Mar 08 '17 at 16:35
@RajeshNavagare, you are probably right, it may be valid but lacks of method scope declaration and could be properly indented. The idea is to make life easier to those people cooperating with you. — LMC, Mar 08 '17 at 16:39
@JohnColeman i totally agree with you, but here my intention was to reduce complexity of iteration. — Rajesh Navagare, Mar 08 '17 at 16:43
@LuisMuñoz Thank you very much. i am new to stack overflow. I think recursion was better tag over there. Thank you again. — Rajesh Navagare, Mar 08 '17 at 16:45

score 2 · Answer 1 · answered Oct 12 '19 at 14:55

Ironically, the method used above i.e. binary recursion computes the Fibonacci number by making two recursive calls in each non-base case. Unfortunately, such a direct implementation of the Fibonacci formula number in this way requires an exponential number of calls to the method.

We are tempted to use the bad recursive formulation because of the way the nth Fibonacci number, F(n), depends on the two previous values, F(n-2) and F(n-1). But notice that after computing F(n-2), the call to compute F(n-1) requires its own recursive call to compute F(n-2), as it does not have the knowledge of value of F(n-2) that was computed at the earlier level of recursion. That is duplicate work. Worse yet, both of these calls will need to (re)compute the value of F(n-3), as will the computation of F(n-1). This snowballing effect is what leads to the exponential running time of fib().

We can compute F(n) much more efficiently using linear recursion in which each invocation makes only one recursive call. To do so, we need to redefine the expectations of the method. Rather than having the method that returns a single value, which is the nth Fibonacci number, we define a recursive method that returns an array with two consecutive Fibonacci numbers {F(n), F(n-1)} using the convention F(-1)=0. Although it seems to be a greater burden to report two consecutive Fibonacci numbers instead of one, passing this extra information from one level of the recursion to the next makes it much easier to continue the process. (It allows us to avoid having to recompute the second value that was already known within the recursion.) An implementation based on this strategy is clearly shown here.

Nick Ziebert · Accepted Answer · 2017-03-28T00:07:01.857

1

Memoization. Create logic that calculates each fib numb only once.

static BigInteger[] fibNumbs = new BigInteger[10000];


public static void main(String[] args) {
        fibNumbs[1] = BigInteger.ONE;
        fibNumbs[2] = BigInteger.ONE;
        System.out.println(fibOf(10000));
    }

public static BigInteger fibOf(int n) {
        if (n <= 1) {
            return BigInteger.ONE;
        }

        if (fibNumbs[n - 1]==null) {
            fibNumbs[n - 1] = fibOf(n - 1);
        }

        if (fibNumbs[n - 2]==null) {
            fibNumbs[n - 2] = fibOf(n - 2);
        }

        return fibNumbs[n - 1].add(fibNumbs[n - 2]);
    }

edited Mar 28 '17 at 00:07

answered Mar 08 '17 at 16:46

Nick Ziebert

1,258
1
9
17

I know this. i want it in code format. see i am returning addition of fib(n-1) and fib(n-2) where fib(n-1) will calculate fib(n-2) in its next call which is needed to stored somewhere so that i can add it. So complexity will be reduced. ternary operator with Array can help but i am expecting more better way. – Rajesh Navagare Mar 08 '17 at 16:51

score 0 · Answer 3 · answered Mar 08 '17 at 21:01

0

If I told you two consecutive fibonacci numbers, eg. a=3 and b=5, could you guess the next? It's the two summed so its 8. Now with a=5 and the newly computed number b=8 you can calculate the next? You start the iteration with the two first 0, 1 and the index of the number you'd like for each iteration you count down and when you hit zero a is your answer. This is a O(n) algorithm.

answered Mar 08 '17 at 21:01

Sylwester

47,942
4
47
79

Yes it can be performed sing single for loop and array for O(n). But my requirement is solution using recursion with less complexity as explained above. Using recursion is bad habit for stack management, i know this but i was asked this to resolve to check my optimised algorithm. – Rajesh Navagare Mar 09 '17 at 03:52
@RajeshNavagare There is not difference between a loop and a recursive function when its recursive call is in tail position and the language supports tail call optimization. Many languages do eg. GNUs extension to C++. The algorithm is the same only instead of updating variables you update the values to the recursive call and the variables are essentially bound arguments. – Sylwester Mar 09 '17 at 09:23

best way to find Fibonacci number

3 Answers3