Given a fibonacci method/function, implement it and make it efficient

Question

Hey guys so in my interview question I was given something like this below. By the way this is my code to solve fib. I want to improve this my code to eliminate repetition of fibonacci sequence that might end up being repeated at the process. For example if fib(1) and fib(1) are repeated twice, how to do I avoid this from happening so the program can advance to unique sequence being processed.

I really want to know how to improve this code. My solution is below but when I debug it, I feel like I get lost understanding what is really happening.

Thanks.

public class Fib {

public static void main(String[] args) {

    System.out.print(fibonacci(14));
}

private static int fibonacci(int n) {

    int fibArray[] = new int[n];
    if (n <= 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    } else {
        fibArray[0] = fibonacci(n - 1);
        fibArray[1] = fibonacci(n - 2);
        if (fibArray[0] == fibonacci(n - 1)) {
            return fibonacci(n - 1) + fibonacci(n - 2);
        } else if (fibArray[1] != fibonacci(n - 2)) {
            return fibonacci(n - 1) + fibonacci(n - 2);

        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }

    }
}

}

Does your code work? If so, you may want to take this http://codereview.stackexchange.com/. If not, please clarify what the problem is. — shmosel, Jul 08 '16 at 22:57
c++? this is c# right? Yes same logic but going to require unique answer to your thread so please remove c++ and the unecessary tag — Khalil Khalaf, Jul 08 '16 at 22:58
Generally speaking, your solution will not work for large N. You have to get rid of recursion and you may do that because you always need only two last values to compute next one. Here you may find nice answer: http://stackoverflow.com/questions/9122277/what-is-a-non-recursive-solution-for-fibonacci-like-sequence-in-java — Pavel S., Jul 08 '16 at 22:59
Is your interview question just to solve Fibonacci, or are there limitations on how you approach it? Because there are (near) `O(1)` ways to find a particular Fibonacci number. — SegFault, Jul 08 '16 at 23:04
@PhotometricStereo I still can't understand the O notation. What is the meaning of your phrase `(near) O(1) ways`? And example? — Khalil Khalaf, Jul 08 '16 at 23:06
In the future, please don't spam question tags. Your question is related to Java, not C++ or C#. Yes, using those unrelated will bring your question more attention, but it will likely be negative attention. — Hovercraft Full Of Eels, Jul 08 '16 at 23:15
@FirstStep Sorry I don't think I will be able to explain it within the number of characters allowed by comments — SegFault, Jul 08 '16 at 23:24
Please take a look at the similar question here, it may be helpful: http://stackoverflow.com/questions/29317414/making-fibonacci-faster — alainlompo, Jul 09 '16 at 18:20

score 2 · Answer 1 · answered Jul 08 '16 at 23:19

To solve the nth Fibonacci number, basic recursion like your answer is not the best way.

There is a complicated matrix method to solve Fibonacci that uses O(log(n)) runtime and O(log(n)) memory.

If you want performance and simplicity in your Fibonacci solution, this is a neat formula (though this is memorization and defeats the problem solving part of the interview):

Here is a Java method implementation:

public Long fibonacci(int n)
{
    double sqrt5 = Math.sqrt(5);

    int tmp1 = (int)(1+sqrt5)/2;
    int tmp2 = (int)(1-sqrt5)/2;

    return (long) Math.ceil((Math.pow(tmp1, n) - Math.pow(tmp2, n))/sqrt5);
}

This method looks O(1) but it's not quite as the Math.pow() is O(log(n)). It uses O(1) memory.

score 1 · Answer 2 · edited May 23 '17 at 12:32

1

As @PavelS mentioned. Should be something similar to this where n is your parameter:

    int a = 0;
    int b = 1;

    // In N steps compute Fibonacci sequence iteratively.
    for (int i = 0; i < n; i++)
    {
        int temp = a;
        a = b;
        b = temp + b;
    }
    return a;

edited May 23 '17 at 12:32

Community

1
1

answered Jul 08 '16 at 23:02

Khalil Khalaf

9,259
11
62
104

score 1 · Answer 3 · answered Jul 08 '16 at 23:11

You need to store the value once computed. If value is present, dont compute again, just use it, else calculate and store:

public class Fib {
    static int fibo[]=new int[100];

    public static void main(String[] args) {

        Arrays.fill(fibo, 0);
        System.out.print(fibonacci(24));
    }

    private static int fibonacci(int n) {
        if (n <= 0) 
            fibo[n]=0;
        else if (n == 1) 
            fibo[n]= 1;
        else if(fibo[n]==0)
            fibo[n]=fibonacci(n-1)+fibonacci(n-2);
        return fibo[n];

    }
}

Stephen C · Answer 4 · 2016-07-09T02:32:11.940

Lets generalize this a little.

There are many techniques that can be used to optimize a recursive function. Here are some of them:

Memoization: you may be able to reduce the cost of repeated calls to an (expensive) function f(n) with the same argument. This can be done by creating a map n -> f(n) and doing a map lookup before making the expensive call.
Converting recursion into iteration. A compiler for a functional programming language will typically do this automatically for simple cases (tail calls). The Java compiler won't (for technical reasons which are off track) ... but you can do the same optimization at the source code level.
Converting call-stack recursion into iteration with a stack-like data structure. This is something you might do in Java to avoid StackOverflowError exceptions in deeply recursive problems that are no amenable to other optimizations.
The solution might be to solve a recurrence relation rather than trying to compute it.

Obviously, not all techniques will work for any given problem.

The other answers give examples of most of approaches.

Approach #1 - @Dip
Approach #2 - @FirstStep
Approach #4 - @PhotometricStereo

Given a fibonacci method/function, implement it and make it efficient

4 Answers4