// Steve J Hodges, Fall 2003
// CS19 example program
// Recurion example: fibonacci numbers
//    don't enter a number too big!

#include <iostream>
using namespace std;

// fn headers
int fib(int); // recursive fibonacci
int fib_i(int); // iterative fibonacci
int fib_c(int); // explicit fibonacci


main(){
  int n, choice;
  cout << "CS19: Fibonacci example" << endl;
  cout << "n ?";
  cin >> n;
  cout << "solution:" << endl;
  cout << "recursive " << fib(n) << endl;
  cout << "iterative " << fib_i(n) << endl;
  cout << "explicit " << fib_c(n) << endl;

}


// calculate fibonacci(n) recursively
// n >= 0 only!
int fib(int n){
  if (n==1 || n==0)
    return n;
  return fib(n-1) + fib(n-2);
}

// calculate fibonacci(n) iterativly
// n >= 0 only!
int fib_i(int n){
  int prev=0;
  int next=1;
  int temp;
  if ( n < 2)
    return n;
  for (int i=2; i<=n; i++){
    temp = prev;
    prev = next;
    next = next + temp;
  }
  return next;
}

// calculate fibonacci(n)
//   consider: Binet's formula 
//   or Lucas Series...
int fib_c(int n){
  return 0;
}