# Fibonacci sequence

• 09-30-2003
girliegti
Fibonacci sequence
Ok, I have to create a program that prints whether a number is in the Fibonacci sequence. This is what i have so far, but i could use some help:

Code:

```#include <iostream> #include <iomanip> using namespace std; int main (void) { int valin, n=0; cout << "Input a positive integer: " << endl; cin>> valin; if (valin==0 || valin==1) cout << "The number" << valin << "is in the Fibonacci sequence." << endl; else if (valin==(n-1)+(n-2)) cout << "The number" << valin << "is in the Fibonacci sequence." << endl; else cout << "The number"  << valin << "in not in the Fibonacci sequence." << endl; return 0; }```
I don't know if this is the best way to go about this problem. Also, is there a way for me to use "bool found=false;" or "char found='N';"
any help would be appreciated, thanks
• 09-30-2003
alpha
have you learned about loops or recursion yet?
• 09-30-2003
girliegti
yes, I've learned for and while loops, but do not totally understand them.
• 09-30-2003
confuted
Have you read the tutorials on them here?
• 09-30-2003
Moni
Watch this ...

Code:

```long fib(int n) { if (n < 2) return n;        //  basis   return fib(n-1) + fib(n-2);  // recursion }```
• 09-30-2003
axon
Quote:

Originally posted by alpha
have you learned about loops or recursion yet?
I would use a for loop instead of recursion. Recursion will give an exponential run time, versus linear for the for structure.
• 09-30-2003
axon
Quote:

Originally posted by Moni
Watch this ...
Code:

```long fib(int n) { if (n < 2) return n;        //  basis   return fib(n-1) + fib(n-2);  // recursion }```

or this:
Code:

```int fib( int n )    //assume  n >= 0 {       if ( n <= 1 ) { return 0; }       int f0 = 0;       int f1 = 1;       int f2;       for( int i = 2; i <= n; i++ ){           f2 = f1 + f0;           f0 = f1;           f1 = f2;       }       return f2; }```
recursion here is innaficient (top code), as it results in exponential time. My code results in linear time...haha...good ol' CS discrete Mathematics.

axon
• 09-30-2003
Zach L.
Restating axon's point:

As a general rule, recursive solutions are elegant and fun to show off. Iterative solutions, on the other hand, are inelegant, but much more efficient in terms of both time and memory.
• 09-30-2003
Moni
At least Recursive solutions look small and easy to understand :)

But of course Iterative solutions are very good with the BIG O Notations ;)