BoeNoe BoeNoe - 8 days ago 5
C++ Question

Recursive Function stops 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 answer = 1;
int recursive(int x);
using std::cout;
using std::cin;
int main() {

recursive( 100000 );

}


int recursive( int x ) {
cout << x << "\n";
answer = x * answer;
x--;
if ( x > 0 ) {
recursive( x );
}
else {
cout << "Answer: " << answer << "\n";
}
}


Is there a way to fix this hindrance?

Answer

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 answer = 1;
int recursive(int x);
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.

Comments