CODEWITHSUNDEEP
c++recursionfibonacci
Ian Burris
Ian Burris

Reputation: 6515

Why is my Recursive Fibonacci implementation written in C++ segfaulting?

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?

Upvotes: 36

Views: 161389

Answers (7)

Pedro Eug&#233;nio
Pedro Eug&#233;nio

Reputation: 39

This is my solution to fibonacci problem with recursion. 

#include <iostream>
using namespace std;

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

int main() {
    cout << fibonacci(8);
    return 0;
}

Upvotes: 2

Vanji
Vanji

Reputation: 1704

By definition, the first two numbers in the Fibonacci sequence are 1 and 1, or 0 and 1. Therefore, you should handle it.

#include <iostream>
using namespace std;

int Fibonacci(int);

int main(void) {
    int number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer.\n";
    else
        cout << number << " Fibonacci is: " << Fibonacci(number) << endl;
}

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

Upvotes: 7

hqt
hqt

Reputation: 30266

I think this solution is short and seem looks nice: 

long long fib(int n){
  return n<=2?1:fib(n-1)+fib(n-2);
}

Edit : as jweyrich mentioned, true recursive function should be: 

long long fib(int n){
      return n<2?n:fib(n-1)+fib(n-2);
    }

(because fib(0) = 0. but base on above recursive formula, fib(0) will be 1)

To understand recursion algorithm, you should draw to your paper, and the most important thing is : "Think normal as often".

Upvotes: 3

noelyahan
noelyahan

Reputation: 4245

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

Upvotes: 2

Dzmitry Huba
Dzmitry Huba

Reputation: 4521

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

Upvotes: 10

Georg Fritzsche
Georg Fritzsche

Reputation: 98964

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...

Upvotes: 151

LiraNuna
LiraNuna

Reputation: 67232

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.

Upvotes: 40

Related Questions