Fibonacci Function Question

Question

I was calculating the Fibonacci sequence, and stumbled across this code, which I saw a lot:

    int Fibonacci (int x)
{
    if (x<=1) {
        return 1;
    }
    return Fibonacci (x-1)+Fibonacci (x-2);
}

What I don't understand is how it works, especially the return part at the end: Does it call the Fibonacci function again? Could someone step me through this function?

Answer 1

Yes, the function calls itself. For example,

Fibonacci(4)
= Fibonacci(3) + Fibonacci(2)
= (Fibonacci(2) + Fibonacci(1)) + (Fibonacci(1) + Fibonacci(0))
= ((Fibonacci(1) + Fibonacci(0)) + 1) + (1 + 1)
= ((1 + 1) + 1) + 2
= (2 + 1) + 2
= 3 + 2
= 5

Note that the Fibonacci function is called 9 times here. In general, the naïve recursive fibonacci function has exponential running time, which is usually a Bad Thing.

Answer 2

This is a classical example of a recursive function, a function that calls itself.

If you read it carefully, you'll see that it will call itself, or, recurse, over and over again, until it reaches the so called base case, when x <= 1 at which point it will start to "back track" and sum up the computed values.

The following code clearly prints out the trace of the algorithm:

public class Test {

    static String indent = "";

    public static int fibonacci(int x) {

        indent += "    ";
        System.out.println(indent + "invoked with " + x);

        if (x <= 1) {

            System.out.println(indent + "x = " + x + ", base case reached.");
            indent = indent.substring(4);

            return 1;
        }

        System.out.println(indent + "Recursing on " + (x-1) + " and " + (x-2));
        int retVal = fibonacci(x-1) + fibonacci(x-2);
        System.out.println(indent + "returning " + retVal);
        indent = indent.substring(4);
        return retVal; 

    }


    public static void main(String... args) {
        System.out.println("Fibonacci of 3: " + fibonacci(3));
    }
}

The output is the following:

invoked with 3
Recursing on 2 and 1
    invoked with 2
    Recursing on 1 and 0
        invoked with 1
        x = 1, base case reached.
        invoked with 0
        x = 0, base case reached.
    returning 2
    invoked with 1
    x = 1, base case reached.
returning 3

Fibonacci of 3: 3

A tree depiction of the trace would look something like

                               fib 4
               fib 3             +           fib 2
    fib 2        +    fib 1              fib 1 + fib 0
fib 1 + fib 0           1                  1       1
  1       1

The important parts to think about when writing recursive functions are:

1. Take care of the base case

What would have happened if we had forgotten if (x<=1) return 1; in the example above?

2. Make sure the recursive calls somehow decrease towards the base case

What would have happened if we accidentally modified the algorithm to return fibonacci(x)+fibonacci(x-1);