BoeNoe - 1 year ago 79
C++ Question

# Reducing usage of stack in recursive function in C++

I have a program that calculates the factorial of any number. When I try to do it to a big number such as 100,000, it stops before it can reach 0. I am guessing this is some sort of safety mechanism to prevent something bad.

While this is good, it prevents the program from calculating huge numbers. In my program, after the variable

`x`
reaches 0, it stops the recursive function. So there is no need for this "safety net".

Here is my code for reference:

``````#include <iostream>
#include <string>

int recursive(int x);
using std::cout;
using std::cin;
int main() {

recursive( 100000 );

}

int recursive( int x ) {
cout << x << "\n";
x--;
if ( x > 0 ) {
recursive( x );
}
else {
}
}
``````

Is there a way to fix this hindrance?

As others have mentioned, you will not be able to fit in factorial of `100,000` into a 64-bit type since it needs about 1.5 million bits to represent it. (It is a number with about `25000` zeroes at the end.)

However, suppose we change the problem to recursive addition from `[1..100000]`. You will still hit the stack issue. The stack is finite and recursion uses the stack, so there is a fundamental limit on the number of calls that you can make.

For something that is as simple as recursion, you can eliminate large uses of the stack by using tail recursion

The code will then need to be changed to:

``````#include <iostream>
#include <string>

int recursive(int multiplier, int x=1);
using std::cout;
using std::cin;

int main() {

std::cout << "Recursion result = " << recursive(100000) << std::endl;

}

int recursive(int multiplier, int x) {
if (multiplier == 1) {
return x;
}
return recursive(multiplier - 1, multiplier * x); // Change the * to + for experimenting with large numbers that could overflow the stack
}
``````

In the above case, since there is no other operation after the recursion, the compiler will optimize and not use up the stack.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download