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

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

Answer 5

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

Answer 6

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

Answer 7

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 8

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 9

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

Answer 10

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 11

My solution is:

#include <iostream>


    int fib(int number);

    void call_fib(void);

    int main()
    {
    call_fib();
    return 0;
    }

    void call_fib(void)
    {
      int input;
      std::cout<<"enter a number\t";
      std::cin>> input;
      if (input <0)
      {
        input=0;
        std::cout<<"that is not a valid input\n"   ;
        call_fib();
     }
     else 
     {
         std::cout<<"the "<<input <<"th fibonacci number is "<<fib(input);
     }

    }





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

    else if (x>0)
   {
        return fib(x-1)+fib(x-2);
    }
    else 
     return -1;
    }

it returns fib(0)=0 and error if negitive

Answer 12

I think it's the best solution of fibonacci using recursion.

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
ull FIBO[100005];
using namespace std;
ull fibo(ull n)
{
    if(n==1||n==0)
        return n;
    if(FIBO[n]!=0)
        return FIBO[n];
    FIBO[n] = (fibo(n-1)+fibo(n-2));
    return FIBO[n];
}
int main()
{
    for(long long  i =34;i<=60;i++)
        cout<<fibo(i)<<" " ;
    return 0;
}

Answer 13

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.