#include <iostream>
using namespace std;
#include "ctimer.h"
#include "prompt.h"

// Illustrates "bad" recursion for computing Fibonacci numbers

const int FIB_LIMIT = 20;            // largest fib # calculated

long RecFib(int n)
// precondition: 0 <= n
// postcondition: returns the n-th Fibonacci number
{
    if (0 == n || 1 == n)
    {   return 1;
    }
    else
    {   return RecFib(n-1) + RecFib(n-2);
    }
}

long Fib(int n)
// precondition: 0 <= n
// postcondition: returns the n-th Fibonacci number
{
    long first=1, second=1, temp;
    int k;
    for(k=0; k < n; k++)
    {   temp = first;
        first = second;
        second = temp + second;
    }
    return first;
}

int main()
{
    CTimer rtimer,itimer;
	int j;
	long  k;
    long ival,rval;
	long iters = PromptRange("enter # of iterations",1L,100000L);
	int limit =  PromptRange("n, for n-th Fibonacci ",1,30);
    
    for(k = 0; k < iters; k++)
    {   for(j=0; j <= limit; j++)
        {   rtimer.Start();
            rval = RecFib(j);
            rtimer.Stop();
            itimer.Start();
            ival = Fib(j);
            itimer.Stop();
            if (ival != rval)
            {   cout << "calls differ for " << j << endl;
                cout << "recursive = " << ival << " iterative = " << rval << endl;
            }
        }
    }
    cout << iters << " recursive trials " << rtimer.CumulativeTime() << endl;
    cout << iters << " iterative trials " << itimer.CumulativeTime() << endl;
    return 0;
}