Recursive Fibonacci

问题:

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?

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

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

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

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

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

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

回答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

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

回答9:

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

回答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!

回答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

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

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