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

if(n==1 || n==0){
    return n;
}else{     
    return fib(n-1) + fib(n-2);
}

However, using recursion to get fibonacci number is bad practice, because function is called about 8.5 times than received number. E.g. to get fibonacci number of 30 (1346269) - function is called 7049122 times!

Answer 2

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

Answer 3

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

in fibonacci sequence first 2 numbers always sequels to 1 then every time the value became 1 or 2 it must return 1

Answer 4

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 5

I think that all that solutions are inefficient. They require a lot of recursive calls to get the result.

unsigned fib(unsigned n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

This code requires 14 calls to get result for fib(5), 177 for fin(10) and 2.7kk for fib(30).

You should better use this approach or if you want to use recursion try this:

unsigned fib(unsigned n, unsigned prev1 = 0, unsigned prev2 = 1, int depth = 2)     
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    if(depth < n) return fib(n, prev2, prev1+prev2, depth+1);
    return prev1+prev2;
}

This function requires n recursive calls to calculate Fibonacci number for n. You can still use it by calling fib(10) because all other parameters have default values.

Answer 6

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.