///////////////////////////////////////////////////////
//
//	fibfactorial.cpp
//
//	Started 5/18/98 by Jeff Ondich
//	Last modified: 10/30/00
//
//	This program illustrates recursive and iterative
//	ways of computing N! and the Nth Fibonacci number.
//
//	1. Read main, figure out what you expect the
//	   program to do, and then compile and run
//	   the program to make sure you were right.
//
//	2. Put the line
//
//		cout << "RecursiveFactorial " << N << endl;
//
//	   at the beginning of the RecursiveFactorial function
//	   (that is, just before the "if( N <= 1 )").
//	   What do you expect to see when you run the program
//	   now?  Try it.  If you see something different from
//	   what you expect, try to figure out why.
//
//	3. Get rid of the cout statement from #2 and put
//	   a similar statement at the beginning of
//	   RecursiveFib.  What do you expect?  What do
//	   you get?  Figure out why.
//
//	4. In terms of N, how many times does
//
////////////////////////////////////////////////////////

#include	<iostream>

// Prototypes.

int IterativeFib( int N );
int RecursiveFib( int N );
int IterativeFactorial( int N );
int RecursiveFactorial( int N );

int main( void )
{
	int			top;
	
	cout << "How high do you want to go? ";
	cin >> top;

	cout << endl << "N\tFib(N)\tN!" << endl;
	cout << "-------------------------" << endl;

	for( int N=1; N <= top; N++ )
	{
		cout	 << N << '\t'
				<< RecursiveFib(N) << '\t'
				<< RecursiveFactorial(N)
				<< endl;
	}
	return( 0 );
}


/////////////////////////////////////////////////////////////
//
//	Returns the Nth Fibonacci number.
//
/////////////////////////////////////////////////////////////

int IterativeFib( int N )
{
	int		previousTerm = 1;
	int		currentTerm = 1;

	for( int i=3; i <= N; i++ )
	{
		int nextTerm = previousTerm + currentTerm;
		previousTerm = currentTerm;
		currentTerm = nextTerm;
	}
	
	return( currentTerm );
}


/////////////////////////////////////////////////////////////
//
//	Returns the Nth Fibonacci number.
//
/////////////////////////////////////////////////////////////

int RecursiveFib( int N )
{
	if( N <= 2 )
		return( 1 );
	else
		return( RecursiveFib(N-1) + RecursiveFib(N-2) );
}


/////////////////////////////////////////////////////////////
//
// Returns N! if N >= 0, and 1 otherwise.
//
/////////////////////////////////////////////////////////////

int IterativeFactorial( int N )
{
	int		product = 1;

	for( int i=2; i <= N; i++ )
		product = product * i;

	return( product );
}


/////////////////////////////////////////////////////////////
//
//	Returns N! if N >= 0, and 1	otherwise.
//
/////////////////////////////////////////////////////////////

int RecursiveFactorial( int N )
{
	if( N <= 1 )
		return( 1 );
	else
		return( N * RecursiveFactorial(N-1) );
}