#include <iostream>

using namespace std;

// recursive solution coded directly from the definition:
// the first two values are 0 and 1, for position after that
// the result is the sum of the previous two values.

int fib1(int pos)
{ if (pos == 0)
    return 0;
  if (pos == 1)
    return 1;
  return fib1(pos-1) + fib1(pos-2); }

int main()
{ while (true)
  { cout << "enter a position: ";
    int x;
    cin >> x;
    const int val = fib1(x);
    cout << "fib(" << x << ") = " << val << "\n"; } }

// once we get to pos = 45 or so, it starts to take "for ever"
// to produce a result. That's because this is an exponential
// algorithm. The number of function calls, and therefore the
// time it takes is roughly proportional to two to-the-power-of
// pos.