#include <iostream>

using namespace std;

/*
 * Program to show recursion, tail recursion
 */
int fact(int n);
int factTail(int n, int product);

int main(){
    int n;
    cout << "enter n: " << endl;
    cin >> n;
    cout << "n factorial is: "<< fact(n) << endl;
    cout << "n factorial is: "<< factTail(n, 1) << endl; //note extra parameter (state variable)

    return 0;
}

/*
 * Recursive, but not tail recursive; every function call must be
 * placed on top of the previous call on the stack, so stack grows
 * with size of n.
 */
int fact(int n){
    if (n < 2)
	return n;
    else
	return n * fact(n - 1); //multiplication has to wait for recursive call to finish
}

/*
 * Tail recursive because there is no deferred operation that has to
 * wait for the recursive call to return. Pass 1 in for initial
 * product value. An optimizing compiler will put successive calls to
 * this function in the same place on the stack, so that stack doesn't
 * grow with size of n
 */
int factTail(int n, int product){
    if (n < 2)
	return product;
    else
	return factTail(n-1, n * product);
}