How to to calculate the factorial of a given integer WITHOUT using recursion.

[cerb63]

I need a little help, I'm still new to the C++ stuff and this is for my class. Any help anyone could give me would be great.
the code I have is as follows:
____________________________________________________________________________

#include <iostream>
using namespace std;

int find_fib(int);    

int main(int argc, char* argv[])
{
  int n=0, result=0;
  cout << "Enter the position in the sequence to find: ";
  cin >> n;
  result = find_fib( n );
  cout << result << " is the " << n << "th Fibonacci sequence number" << endl;
  system("pause");
  return 0;
}

int find_fib( int n )
{
  if(n < 3)
    return 1;
  else
    return( find_fib(n - 2) + find_fib( n - 1 ) );
}

[chococrack]

1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 2! x 3 = 6
N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

Could this help?

A guess:

int theFact = 1;
for(int i=N; i>0; i--)
{
     theFact *= i;
}

return theFact;

[stilllearning]

Did you want to try and do a non-recursive factorial or a non-recursive way to compute the fibonacci ? Please put tags around your code.

And for a non-recursive fibonacci. You could do something like this

int fib(int n){

  int previous = -1;
  int result   = 1;
  int sum;

  for(int i = 0; i <= n; i++){
    sum = previous + result;
    previous = result;
    result   = sum;
  }

  return result;
}

[sidatra79]

Hallo
I post u a solution to your problem divided into three parts:

Part A: Includes your solution exactly the way you posted it. However it is an inefficient recursive solution, because it has an exponential performance.
Part B: Includes an optimized recursive solution using the help of a wrapper function which results into a O(n) performance.
Part C: Includes an non-recursive (iterative) solution.

In addition i measure the execution time for all three of them.
U can notice like expected that Part A is a bad solution.....
see here the results for finding the 42th Fibonacci number:

Enter the position in the sequence to find: 42
A: Your function gives: 267914296 is the 42th Fibonacci sequence number
The execution time of the PART A is = 4563 msecs
B: Optimized function gives: 267914296 is the 42th Fibonacci sequence number
The execution time of the PART B is = 0 msecs
C: Iterative function gives: 267914296 is the 42th Fibonacci sequence number
The execution time of the PART C is = 0 msecs

So here is the code (no errors or warnings):

#include <iostream>
#include <ctime> //for calculating execution time

double diffclock(time_t ,time_t ); //for calculating execution time
int find_fib(int);    
unsigned long double fibWrapper(int);
unsigned long double fibo_find_2 (unsigned long double, unsigned long double, int);
unsigned long double fibo_find_3_NonRecursive(int);

int main(int argc, char* argv[])
{
	//Required for measuring execution perfomance
	time_t startTime1,endTime1,startTime2;
        time_t endTime2,startTime3,endTime3;
	double elapsedTime1,elapsedTime2,elapsedTime3;

	int n=0;
	unsigned long double result=0;
	std::cout << "Enter the position in the sequence to find: ";
	std::cin >> n;
	
	//PART A:
	startTime1 = clock();	//Start measuring execution time
	result = find_fib(n);
	endTime1 = clock();	//Stop measuring execution time
       //Get total execution time in msec	
        elapsedTime1 = diffclock(endTime1,startTime1);
	std::cout <<"A: Your function gives: "<< result << " is the " 
                     << n << "th Fibonacci sequence number" << std::endl;
	std::cout<<"The execution time of the PART A is = "<<elapsedTime1
                    <<" msecs"<<std::endl;
	result = 0;
	
	//PART B:
	startTime2 = clock();	//Start measuring execution time
	result = fibWrapper(n);
	endTime2 = clock();	//Stop measuring execution time
       //Get total execution time in msec
	elapsedTime2 = diffclock(endTime2,startTime2);
	std::cout <<"B: Optimized function gives: " <<result << " is the " 
                     << n << "th Fibonacci sequence number" << std::endl;
	std::cout<<"The execution time of the PART B is = "<<elapsedTime2
                     <<" msecs"<<std::endl;
	result = 0;

	//PART C:
	startTime3 = clock();	//Start measuring execution time
	result = fibo_find_3_NonRecursive(n);	
	endTime3 = clock();	//Stop measuring execution time
        //Get total execution time in msec
	elapsedTime3 = diffclock(endTime3,startTime3);
	std::cout <<"C: Iterative function gives: " <<result << " is the " 
                      << n << "th Fibonacci sequence number" << std::endl;
	std::cout<<"The execution time of the PART C is = "<<elapsedTime3
                     <<" msecs"<<std::endl;
	
	return 0;
}
// PART A:
//Your recursive solution: Correct BUT VERY INEFFICIENT exponential performance
unsigned long double find_fib( int n )
{
	if(n < 3)
		return 1;
	else
		return( find_fib(n - 2) + find_fib( n - 1 ) );
}

//PART B:
//Optimized recursive solution: Correct and with O(n) performance
unsigned long double fibo_find_2(unsigned long double fibCurr,unsigned long double fibPrev, int n) //is called indirectly throuth the wrapper function
{
	//fibCurr: the current fibonacci Number
	//fibPrev: the previous fibonacci number
	//n: the number of the fibonacci numbers left to calculate
	if(n == 1)
		return fibCurr;
	else
		return fibo_find_2(fibCurr+fibPrev,fibCurr, n-1);
}
//The wrapper function for calculating fibonacci numbers
unsigned long double fibWrapper (int n)
{
//returns the value of the nth fibonacci number
	return fibo_find_2(1, 0, n);
}

//PART C:
////Non recursive==Iterative solution
unsigned long double fibo_find_3_NonRecursive (int n)
{
	unsigned long double localresult = 1;
	unsigned long double temp1 = 1;
	unsigned long double temp2 = 0;

	for (int k=3;k<=n;k++)
	{
		temp2 = localresult;
		localresult +=  temp1;
		temp1 = temp2;
	}
	return localresult;
}
//Nedded for calculating the execution time
double diffclock(time_t clock1,time_t clock2) //Using time_t & difftime
{
	double diffticks=difftime(clock1,clock2); 
	double diffms=(diffticks)/(CLOCKS_PER_SEC/1000);
	return diffms;
}

NOTE: if sbdy thinks that the way I calculate the execution time is inaccurate please provide an optimized and tested alternative. I tested on my machine with ACE timers but I think its not an solution available for all people.

[Salem]

Which compiler allows the nonsense "unsigned long double" as a declaration?

[stilllearning]

Strangely MSVC++ 2008 does allow it .. although gcc does not.

[sidatra79]

Come on guys
It was "long Double" just used the "replace all" replacing "long" with "unsigned long" having not noticed the double there... ;) ;)
and like u correctly said in VS 2008 gave me the compiler no clue to notice that...

But what about the rest
Is it also nonsense:@ ????

[Salem]

Rest seems fine.