Thread: Help understanding: using recursion and dynamic data sturcture stack

You are going to write a C program and use recursion as well as a dynamic data structure stack in this question.
Here is my homework assigment.

Factorial of a number is calculated as
n ! = n x (n‐1) x (n‐2) x (n‐3) x ... x 1

First, write a C program to implement the factorial operation using recursion. Name this first file as yourFirstName‐LastName‐recursive.c. Run your first program for n=1, 2, 3, ..., 12 and record runtime (in msec) for each execution. For calculating runtime, please make a search and add a runtime calculator code to your C program.

Then, write another C program to calculate the factorial of a given number using stack this time. Name this first file as yourFirstName‐LastName‐with‐stack.c. Run your second program for n=1, 2, 3, ..., 12 nd record runtime (in msec) for each execution. For calculating runtime, please use the same runtime alculator code you have used above and add it to your C code.

Help me understand what am i suppose to do please. I just started stacks but have no idea how I can calculate the run time, is it already in c?

Thanks for the help as usual.

should I do something like this to measure time? the thing is it measures it in seconds they want int m seconds.

How about dividing by 1000?
This will only work if diff is > 1 though.
I think there's no standard way.
for POSIX, you can use gettimeofday.
For windows, refer to CT post.

ok here is what I have so far and is not working I get zero for every factorial even 12! which I think should take some time. I have it set to zero since I have not figured out a way to time each factorial when going trough the loop.

Code:

#include <stdio.h>
#include <sys/timeb.h>

long factorial(long number);


int main (void){



  struct timeb time_start, time_current;
  int milliseconds_difference;

  int i;


	for(i=12;i<=12;i++){

	
ftime(&time_start);
	 factorial(i);

ftime(&time_current);


int milliseconds_difference = (time_current.millitm + (1000 * seconds_difference)) - time_start.millitm;
	 

	 
		printf("%2d = %ld\n", i, factorial(i));
		
	printf("It took %.d m. seconds to calculate %2d!\n", milliseconds_difference, i );

	}




return 0;

}

long factorial (long number)
{

 if (number <=1){
	return 1;
 }

 else {

	return ( number * factorial( number -1));

 }

}

Here is another failed try.

Code:

#include <stdio.h>
#include <time.h>

long factorial(long number);
double diffclock(clock_t clock1,clock_t clock2);


int main (void){


  
clock_t clock3, clock4;
    
     




  
  

  int i;
clock3 = clock();


	for(i=0;i<=12;i++){

	 

	 factorial(i);

	 



	 

	 
		printf("%2d = %ld\n", i, factorial(i));
		
	printf("It took  m.seconds to calculate %2d!\n", i );

	}



clock4 = clock() ;

printf("%f m.seconds\n", diffclock(clock3,clock4) );

return 0;

}















long factorial (long number)
{

 if (number <=1){
	return 1;
 }

 else {

	return ( number * factorial( number -1));

 }
}


double diffclock(clock_t clock1,clock_t clock2)

The problem here is your clock is simply far too slow to measure anything as fast as it takes to run a simple function. You're basically trying to time a bullet from a gun using a sundial.

Unless you do something, it always looks like zero.

Try this

Code:

for(i=0;i<=12;i++){
  int result;
  clock1 = clock();
  for ( j = 0 ; j < 1000000 ; j++ ) {
    result = factorial(i);
  }
  clock2 = clock();
  // clock2 - clock1 is the time for 1M calls
  // divide this by 1M to get the time for 1 call.
}

ok I tried with the 1m loop, but now i'm getting negative nums.

Code:

#include <stdio.h>
#include <time.h>

long factorial(long number);
double diffclock(clock_t clock1,clock_t clock2);


int main (void){


  
clock_t clock3, clock4;
    
     




  
  

  int i;
  int j;


	for(i=0;i<=12;i++){

	 clock3 = clock();

		 for ( j = 0 ; j < 1000000 ; j++ ) {
   
	 	 factorial(i);

	 
		 }
		 clock4 = clock() ;

	 

	 
		printf("%2d = %ld\n", i, factorial(i));
		
	printf("It took  %f m.seconds to calculate %2d!\n" , diffclock(clock3,clock4), i );

	}







return 0;

}















long factorial (long number)
{

 if (number <=1){
	return 1;
 }

 else {

	return ( number * factorial( number -1));

 }
}

That's because you're subtracting the last time (which is bigger) from the first time.

You know, better variable names like 'before' and 'after' would make it obvious.
As opposed to clock1234

Also, indent your code properly. It's only 20 lines, but it's still a mess.