Recursive Fibonacci

Question

I'm having a hard time understanding why

#include <iostream>

using namespace std;

int fib(int x) {
    if (x == 1) {
        return 1;
    } else {
        return fib(x-1)+fib(x-2);
    }
}

int main() {
    cout << fib(5) << endl;
}

results in a segmentation fault. Once x gets down to 1 shouldn't it eventually return?

Answer 1

When x==2 you call fib(1) and fib(0):

return fib(2-1)+fib(2-2);

Consider what will happen when fib(0) is evaluated...

Answer 2

The reason is because Fibonacci sequence starts with two known entities, 0 and 1. Your code only checks for one of them (being one).

Change your code to

int fib(int x) {
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2);
}

To include both 0 and 1.

Answer 3

Why not use iterative algorithm?

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}

Answer 4

So I was checking out this meta-programming thing that LiraNuna was talking about in the comments of this answer. Taking in the syntax examples, the Fibonnaci can be calculated in compile time with the following:

template <int N>
struct Fibonnaci 
{
    enum { value = Fibonnaci<N - 1>::value + Fibonnaci<N - 2>::value };
};

template <>
struct Fibonnaci<1> 
{
    enum { value = 1 };
};

template <>
struct Fibonnaci<0> 
{
    enum { value = 0 };
};

// Fibonnaci<4>::value == 0+1+1+2 = 3
// Fibonnaci<0>::value == 0

Haven't checked if this compiles and works though.

Answer 5

"The OP never asked for another solution to the fibonacci generation problem, he just asked for some help to debug his code".

Personally I should also like a better algorithm.

See exercise 7.11 and 9.4 : http://www.oopschool.com/books/CPB2010.pdf

Best regards Kjell Bleivik