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

have you learned about loops or recursion yet?

yes, I've learned for and while loops, but do not totally understand them.

Have you read the tutorials on them here?

Watch this ...

Code:

---

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

---

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.

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

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.

At least Recursive solutions look small and easy to understand :)

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