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

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);

Answer 2

This is classic function recursion. http://en.wikipedia.org/wiki/Recursive_function should get you started. Essentially if x less than or equal to 1 it returns 1. Otherwise it it decreases x running Fibonacci at each step.

Answer 3

Yes, the Fibonacci function is called again, this is called recursion.

Just like you can call another function, you can call the same function again. Since function context is stacked, you can call the same function without disturbing the currently executed function.

Note that recursion is hard since you might call the same function again infinitely and fill the call stack. This errors is called a "Stack Overflow" (here it is !)

Answer 4

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 5

In C and most other languages, a function is allowed to call itself just like any other function. This is called recursion.

If it looks strange because it's different from the loop that you would write, you're right. This is not a very good application of recursion, because finding the n th Fibonacci number requires twice the time as finding the n-1th, leading to running time exponential in n.

Iterating over the Fibonacci sequence, remembering the previous Fibonacci number before moving on to the next improves the runtime to linear in n, the way it should be.

Recursion itself isn't terrible. In fact, the loop I just described (and any loop) can be implemented as a recursive function:

int Fibonacci (int x, int a = 1, int p = 0) {
    if ( x == 0 ) return a;
    return Fibonacci( x-1, a+p, a );
} // recursive, but with ideal computational properties

Answer 6

return Fibonacci (x-1)+Fibonacci (x-2);

This is terribly inefficient. I suggest the following linear alternative:

unsigned fibonacci(unsigned n, unsigned a, unsigned b, unsigned c)
{
    return (n == 2) ? c : fibonacci(n - 1, b, c, b + c);
}

unsigned fibonacci(unsigned n)
{
    return (n < 2) ? n : fibonacci(n, 0, 1, 1);
}

The fibonacci sequence can be expressed more succinctly in functional languages.

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

> take 12 fibonacci
[0,1,1,2,3,5,8,13,21,34,55,89]

Answer 7

As your question is marked C++, I feel compelled to point out that this function can also be achieved at compile-time as a template, should you have a compile-time variable to use it with.

template<int N> struct Fibonacci {
    const static int value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value;
};
template<> struct Fibonacci<1> {
    const static int value = 1;
}
template<> struct Fibonacci<0> {
    const static int value = 1;
}

Been a while since I wrote such, so it could be a little out, but that should be it.