Reducing usage of stack in recursive function in C++

Question

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 1

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 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.

Answer 2

Maybe I'm a bit too late but I'll nevertheless add my advices and solutions. It may help you (and others) another time.
The best solution to the stackoverflow problem is actually not to use recursion at all:

int fac(int n){
    int res=1;
    for(int i = 0; i <= n; ++i){
        res *= i;
    }
    return res;
}

Recursion is actually discommanded while programming because of the time(function calls) and ressources(stack) it consumes. In many cases recursion can be avoided by using loops and a stack with simple pop/push operations if needed to save the "current position" (in c++ one can use a vector). In the case of the factorial, the stack isn't even needed but if you are iterating over a tree datastructure for example you'll need a stack (depends on the implementation though).

Now the other problem you have is the limitation of the size of int: you can't go above fac(12) if you are working with 32-bits integers and not above fac(20) for 64-bits integers. This can be solved by using external libraries that implements operations for big numbers (like the GMP library or Boost.multiprecision as SenselessCoder mentionned). But you could also create your own version of a BigInteger-like class from Java and implement the basic operations like the one I have. I've only implemented multiplication in my example but the addition is quite similar:

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
using namespace std;


class BigInt{
    // Array with the parts of the big integer in little endian
    vector<int> value;
    int base;
    void add_most_significant(int);
    public:
        BigInt(int begin=0, int _base=100): value({begin}), base(_base){ };
        ~BigInt(){ };
        /*Multiply this BigInt with a simple int*/
        void multiply(int);
        /*Print this BigInt in its decimal form*/
        void print();
};

void BigInt::add_most_significant(int m){
    int carry = m;
    while(carry){
        value.push_back(carry % base); 
        carry /= base;
    }
}

void BigInt::multiply(int m){
    int product = 0, carry = 0;
    // the less significant part is at the beginning
    for(int i = 0; i < value.size(); i++){
        product = (value[i] * m) + carry;
        value[i] = product % base;
        carry = product/base;
    }
    if (carry)
        add_most_significant(carry);
}

void BigInt::print(){
    // string for the format depends on the "size" of the base (trailing 0 in format => fill with zeros if needed when printing)
    string format("%0" + to_string(to_string(base-1).length()) + "d");

    // Begin with the most significant part: outside the loop because it doesn't need trailing zeros
    cout << value[value.size()-1];
    for(int i = value.size() - 2; i >= 0; i-- ){
        printf(format.c_str(), value[i]);
    }
}

The main idea is simple, a BigInt represents a big decimal number by cutting its little endian representation into pieces. The length of those pieces depends on the base you choose. It will only work if your base is a power of 10: if you choose 10 as base each piece will represent one digit, if you choose 100 (= 10^2) as base each piece will represent two consecutive digits starting from the end(see little endian), if you choose 1000 as base (10^3) each piece will represent three consecutive digits, ... and so on. Let's say that you have base 100, 12765 will then be [65, 27, 1], 1789 will be [89, 17], 505 will be [5, 5] (= [05,5]), ... with base 1000: 12765 would be [765, 12], 1789 would be [789, 1], 505 would be [505].
The multiplication is then a bit like the multiplication on paper we learned at school:

1. begin with the lowest piece of the BigInt
2. multiply it with the multiplier
3. the lowest piece of that product (= the product modulus the base) becomes the corresponding piece of the final result
4. the "bigger" pieces of that product will be added to the product of the following pieces
5. go to step 2 with next piece
6. if no piece left, add the remaining bigger pieces of the product of the last piece of the BigInt to the final result

For example:

9542 * 105 = [42, 95] * 105
    lowest piece = 42 --> 42 * 105 = 4410 = [10, 44]
                ---> lowest piece of result = 10
                ---> 44 will be added to the product of the following piece
    2nd piece = 95    --> (95*105) + 44 = 10019 = [19, 00, 1]
                ---> 2nd piece of final result = 19
                ---> [00, 1] = 100 will be added to product of following piece
    no piece left --> add pieces [0, 1] to final result
==> 3242 * 105 = [42, 32] * 105 = [10, 19, 0, 1] = 1 001 910

If I use the class above to calculate the factorials of all numbers between 1 and 30 as shown in the code below :

 int main() {
    cout << endl << "Let's start the factorial loop:" << endl;
    BigInt* bigint = new BigInt(1);
    int fac = 30; 
    for(int i = 1; i <= fac; ++i){
        bigint->multiply(i);
        cout << "\t" << i << "! = ";
        bigint->print();
        cout << endl;
    }
    delete bigint;
    return 0;
}

it will give the following result:

Let's start the factorial loop:
    1! = 1
    2! = 2
    3! = 6
    4! = 24
    5! = 120
    6! = 720
    7! = 5040
    8! = 40320
    9! = 362880
    10! = 3628800
    11! = 39916800
    12! = 479001600
    13! = 6227020800
    14! = 87178291200
    15! = 1307674368000
    16! = 20922789888000
    17! = 355687428096000
    18! = 6402373705728000
    19! = 121645100408832000
    20! = 2432902008176640000
    21! = 51090942171709440000
    22! = 1124000727777607680000
    23! = 25852016738884976640000
    24! = 620448401733239439360000
    25! = 15511210043330985984000000
    26! = 403291461126605635584000000
    27! = 10888869450418352160768000000
    28! = 304888344611713860501504000000
    29! = 8841761993739701954543616000000
    30! = 265252859812191058636308480000000

My appologies for the long answer. I tried to be as brief as possible but still be complete. Questions are always welcome
Good luck!

Answer 3

I can suggest a couple of things for some problems you're seeing.

The problem that you are not getting to evaluate every recursive step is because you are having a stack overflow. This happens when use more stack space than you're meant to do. You can avoid this by keeping a table of previously calculated values. Notice that it won't help if you immediately want to calculate 100000's factorial, but if you slowly climb up to that by calculating, for example, 10!, then 20! etc. you won't have this problem. An additional thing to do would be to increase your stack size. I saw some comments regarding this, so I won't mention how.

The next problem you'll run into is that you'll be unable to represent the numbers that come as the result of the factorial. This is because your integer size is not enough to represent these numbers. In other words, you're overflowing the integer. For this, and also the point above, you can see this: Boost.multiprecision. Boost is a very nice library that you can use for things like this.