What is wrong with my Java recursive fibonacci function?

Question

I've just written this piece but for some reason in the console I get some numbers which look right but are in the wrong order, and some numbers are repeated. What is the problem?

public class Fibonacci {
    public static void main(String[] args) {
        int n = 5;

        fibonacci(n);
    }

    public static int fibonacci(int n) {
        if(n == 0) {
            System.out.println(0);
            return 0;
        } else if(n == 1) {
            System.out.println(1);
            return 1;
        } else {
            int result = fibonacci(n - 1) + fibonacci(n - 2);
            System.out.println(result);
            return result;
        }
    }
}

Could you add some test cases? Like, "results for test n=0, results for test n=1..." etc? — ebwb
– ebwb, Commented May 12, 2015 at 20:17

Shar1er80 · Accepted Answer · 2015-05-12 20:27:28Z

1

If you're wanting to see the Fibonacci sequence up to the set term, remove all outputs from your fibonacci(int n) method and just have one print method in main that is in a for loop from 1 up to your set term.

public static void main(String[] args) {
    int n = 5;

    for (int i = 1; i <= n ; i++) {
        System.out.print(fibonacci(i) + " ");
    }
}

public static int fibonacci(int n) {
    if(n == 0) {
       return 0;
    } else if(n == 1) {
       return 1;
    } else {
       return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Results:

enter image description here

answered May 12, 2015 at 20:27

Shar1er80

9,0512 gold badges24 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

rgettman · Accepted Answer · 2015-05-12 20:18:06Z

Your program calculates the Fibonacci number correctly. It's the last number printed, in the top-level call to fibonacci.

Some numbers are repeatedly printed because they are being calculated more than once. fibonacci(5) calls fibonacci(4) + fibonacci(3), which calls fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1), and we already have two separate recursive calls that have the same argument. There are more repeated calls as the recursive calls descend further.

For a low input such as 5, this is ok, but for higher numbers, you will have performance problems, because this algorithm is exponential in nature. The complexity is O(2ⁿ). Your current print statements are highlighting all the extra calculations that are being performed. You can remove them, but the algorithm is still exponential in complexity.

Even though your program is currently correct, it is possible to eliminate the exponential complexity, replacing it with linear complexity (O(n)), by storing the results of intermediate calls to fibonacci in an array. This way, each intermediate step is only calculated once.

duffymo · Accepted Answer · 2015-05-12 20:18:08Z

0

I'd advise that you remove those print statements. They are confusing you.

This is the way recursion works: you pop method calls off the stack to evaluate them.

This looks fine to me:

public class Fibonacci {
    public static void main(String[] args) {
        int n = 10;

        for (int i = 0; i < n; ++i) {
            System.out.println(String.format("i: %5d fib(i): %10d", i, fibonacci(i)));
        }
    }

    public static int fibonacci(int n) {
        if(n == 0) {
            return 0;
        } else if(n == 1) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

answered May 12, 2015 at 20:18

duffymo

310k46 gold badges376 silver badges571 bronze badges

Comments

aebabis · Accepted Answer · 2015-05-12 20:19:13Z

Since your function is recursive, there are multiple prints per fibonacci number. If you don't want this, move the printing outside the function

public class Fibonacci {
    public static void main(String[] args) {
        int n = 5;

        System.out.println(fibonacci(n));
    }

    public static int fibonacci(int n) {
        if(n == 0) {
            return 0;
        } else if(n == 1) {
            return 1;
        } else {
            int result = fibonacci(n - 1) + fibonacci(n - 2);
            return result;
        }
    }
}

If, however, you intended the prints for tracing what the function does, then it is already behaving as expected. Recursive fibonacci computes the same values multiple times, which is why it is so inefficient.

J Atkin · Accepted Answer · 2015-05-12 20:41:12Z

0

Your method is perfectly fine, the extra prints are from the recursive calls to your fibonacci method. The call stack of fib for 4 is:

                         f(4)
                  /                 \
          f(4-1)          +            f(4-2)
        /          \                /         \
   f(3-1)   +     f(3-2)  +      f(2-1)  +  f(2-2)
    /      \        |               |          |
 f(2-1) + f(2-2)    |               |          |
    |        |      |               |          |
    1   +    0  +   1      +        1     +    0
                        3

(Note: f is short for fibonacci)

Each one of the calls prints to the console, resulting in the extra and out of order numbers.

edited May 12, 2015 at 20:41

answered May 12, 2015 at 20:31

J Atkin

3,1803 gold badges22 silver badges33 bronze badges

Collectives™ on Stack Overflow

What is wrong with my Java recursive fibonacci function?

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related