Recursive Fibonacci

Question

I m having a hard time understanding why   include  lt iostream gt   using namespace std   int fib int x        if  x    1            return 1        else           return fib x-1  fib x-2            int main         cout  lt  lt  fib 5   lt  lt  endl      results in a segmentation fault  Once x gets down to 1 shouldn t it eventually return

User · Answer

I think it s the best solution of fibonacci using recursion    include lt bits stdc   h gt  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 lt  60 i            cout lt  lt fibo i  lt  lt           return 0

User · Answer

By definition  the first two numbers in the Fibonacci sequence are 1 and 1  or 0 and 1  Therefore  you should handle it    include  lt iostream gt  using namespace std   int Fibonacci int    int main void        int number       cout  lt  lt   Please enter a positive integer         cin  gt  gt  number      if  number  lt  0          cout  lt  lt   That is not a positive integer  n       else         cout  lt  lt  number  lt  lt    Fibonacci is     lt  lt  Fibonacci number   lt  lt  endl     int Fibonacci int x         if  x  lt  2        return x                 return  Fibonacci  x - 1    Fibonacci  x - 2

User · Answer

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

User · Answer

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

User · Answer

This is my solution to fibonacci problem with recursion        include  lt iostream gt  using namespace std   int fibonacci int n       if n lt  0          return 0      else if n  1    n  2          return 1      else         return  fibonacci n-1  fibonacci n-2       int main         cout  lt  lt  fibonacci 8       return 0

User · Answer

I think this solution is short and seem looks nice    long long fib int n     return n lt  2 1 fib n-1  fib n-2       Edit   as jweyrich mentioned  true recursive function should be    long long fib int n         return n lt 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

User · Answer

int fib int x         if  x  lt  2        return x      else        return  fib x - 1    fib x - 2

User · Answer

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

User · Answer

Why not use iterative algorithm   int fib int n        int a   1  b   1      for  int i   3  i  lt   n  i              int c   a   b          a   b          b   c                       return b

User · Answer

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

User · Answer

My solution is    include  lt iostream gt        int fib int number        void call fib void        int main             call fib        return 0             void call fib void              int input        std  cout lt  lt  enter a number t         std  cin gt  gt  input        if  input  lt 0                  input 0          std  cout lt  lt  that is not a valid input n              call fib                else                  std  cout lt  lt  the   lt  lt input  lt  lt  th fibonacci number is   lt  lt fib input                          int fib int x             if  x  0  return 0        else if  x  2    x  1                 return 1                else if  x gt 0               return fib x-1  fib x-2             else       return -1          it returns fib 0  0 and error if negitive

User · Answer

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

User · Answer

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

[c++] Recursive Fibonacci

Examples related to c++

Examples related to recursion

Examples related to fibonacci