/* Filename:  fib.cpp

   Author:  Br. David Carlson

   Date:  March 8, 1998

   Last Modified:  November 28, 2001

   This program allows the user to repeatedly find any desired Fibonacci
   number.  The user is prompted to enter the index n of the desired one.
   The nth Fibonacci number is then printed on the screen.  Actually, it
   is computed and printed twice, first by using an iterative Fibonacci
   function and then using a recursive Fibonacci function.

   Try various small values for n.  Then try some values in the 30's.
   Note how the recursive version starts to take significantly longer
   than the iterative one.

   Tested with:
      Microsoft Visual C++ 6.0
      Microsoft Visual C++ .NET
      g++ under Linux
*/

#include <iostream>
using namespace std;


// Function prototypes:

long fib1(int n);  
long fib2(int n);


int main(void)
   {
   int n;
   long answer;

   cout << "Enter a (not too large) non-negative integer or -1 to quit: ";
   cin >> n;

   while (n != -1)
      {
      answer = fib1(n);
      cout << "Using the iterative Fibonacci function..." << endl;
      cout << "The nth Fibonacci number when n is " << n << " is "
         << answer << endl << endl;

      answer = fib2(n);
      cout << "Using the recursive Fibonacci function..." << endl;
      cout << "The nth Fibonacci number when n is " << n << " is "
         << answer << endl << endl;

      cout << "Enter a (not too large) non-negative integer"
         << " or -1 to quit: ";
      cin >> n;
      }

   return 0;
   }


/* Given:  n  A non-negative integer.
   Task:   To find the nth Fibonacci number.
   Return: This Fibonacci number in the function name.
*/
long fib1(int n)
   {
   // This function uses iteration, not recursion.
   int k;
   long FibA, FibB, Sum;

   FibA = 0;
   FibB = 1;

   for (k = 0; k < n; k++)
      {
      Sum = FibA + FibB;
      FibA = FibB;
      FibB = Sum;
      }

   return FibB;
   }


/* Given:  n  A non-negative integer.
   Task:   To find the nth Fibonacci number.
   Return: This Fibonacci number in the function name.
*/
long fib2(int n)
   {
   if ((n == 0) || (n == 1))      // stopping cases
      return 1;
   else                           // recursive case
      return fib2(n - 1) + fib2(n - 2);
   }