#include <iostream>

using namespace std;

// this is a nice clean solution that remembers the two previous
// values instead of recomputing them. It is back to running in
// "no time at all".   

int fib2(int pos, int prev, int prevprev)
{ if (pos == 0)
    return prev + prevprev;
  return fib2(pos-1, prev+prevprev, prev); }

int fib2(int pos)
{ if (pos <= 1)
    return pos;
  return fib2(pos-2, 1, 0); }

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