The following code is a tail recursive solution to the problem
of finding the factorial of a positive integer. The factorial function in
this example uses two arguments including acc which holds the
accumulated intermediate value of the solution. By using a static variable,
as in the second section of code below, the accumulator can be eliminated.
The neatness of the result may be debated.
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef unsigned long ulong;
ulong factorial (int n, ulong acc) {
if (n <= 0) return acc;
return factorial (n1, acc*n);
}
int main (int argc, char **argv) {
if (argc != 2) {
cout << "Usage: " << argv[0] <<
" <positiveinteger>\n";
exit (0);
}
int n = atoi(argv[1]);
cout << n << "! = " <<
factorial(n, 1) << "\n";
}
This section of code uses a static variable to eliminate the need for the
acc argument.
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef unsigned long ulong;
ulong factorial (int n) {
static ulong acc = 1;
if (n <= 0) return acc;
acc *= n;
return factorial (n1);
}
int main (int argc, char **argv) {
if (argc != 2) {
cout << "Usage: " << argv[0] <<
" <positiveinteger>\n";
exit (0);
}
int n = atoi(argv[1]);
cout << n << "! = " <<
factorial(n) << "\n";
}
Here is a similar result for Fibonacci code. The first section has two
accumulators and the second two static variables.
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef unsigned long ulong;
ulong fib (int n, ulong x, ulong y) {
if (n <= 1) return x;
return fib(n1, x+y, x);
}
int main (int argc, char **argv) {
if (argc != 2) {
cout << "Usage: " << argv[0] <<
" <positiveinteger>\n";
exit (0);
}
int n = atoi(argv[1]);
cout << "fib(" << n << ") = " <<
fib(n, 1, 1) << "\n";
}
Here is the section using the static variables.
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef unsigned long ulong;
ulong fib (int n) {
static ulong x = 1, y = 1;
if (n <= 1) return x;
ulong t = x;
x += y;
y = t;
return fib(n1);
}
int main (int argc, char **argv) {
if (argc != 2) {
cout << "Usage: " << argv[0] <<
" <positiveinteger>\n";
exit (0);
}
int n = atoi(argv[1]);
cout << "fib(" << n << ") = " <<
fib(n) << "\n";
}
