I have this program that times iterative and recursive solutions. I need to use
ID: 3536539 • Letter: I
Question
I have this program that times iterative and recursive solutions. I need to use this function: C(n, r) = n! / (r! * (n-r)!). I have the recursive function I just need help doing the iterative but I have no idea of the difference, also what am I missing in my code? Code and explanations would be much appreciated!
1 #include <iostream>
2 #include <sys/time.h>
3 #include <cstdlib>
4
5 using std::cout;
6 using std::endl;
7 using std::cin;
8
9 unsigned long factorial (unsigned long n, unsigned long r){
10 if (n == r || r == 0)
11 return 1;
12 else
13 {
14 return factorial (n - 1, r) + factorial( n - 1, r - 1);
15 }
16 }
17
18 int main() {
19 struct timeval stop, start;
20 int n, r;
21 unsigned long output;
22 cout << "Enter n, r: ";
23 cin >> n;
24 cin >> r;
25 gettimeofday (&start , NULL);
26
27 output = factorial(n) / (factorial (r)* factorial(n - r));
28
29 gettimeofday(&stop, NULL);
30 cout << " Total is: " << output << endl << "Total Time: " << stop.tv_usec - start.tv _usec << endl;
31 return 0;
32 }
Explanation / Answer
1 #include <iostream>
2 #include <sys/time.h>
3 #include <cstdlib>
4
5 using std::cout;
6 using std::endl;
7 using std::cin;
8
9 unsigned long factorial (unsigned long n){// change in parameter
10 if (n == 1)
11 return 1;
12 else
13 {
14 return n* factorial( n - 1); // calculation to calculate factorial.....using recursion
15 }
16 }
17
18 int main() {
19 struct timeval stop, start;
20 int n, r;
21 unsigned long output;
22 cout << "Enter n, r: ";
23 cin >> n;
24 cin >> r;
25 gettimeofday (&start , NULL);
26
27 output = factorial(n) / (factorial (r)* factorial(n - r));
28
29 gettimeofday(&stop, NULL);
30 cout << " Total is: " << output << endl << "Total Time: " << stop.tv_usec - start.tv _usec << endl;
31 return 0;
32 }