Reducing stack usage in recursive function in C ++

Question

I have a program that calculates the factorial of any number. When I try to do this to a large amount, such as 100,000, it stops before it reaches 0. I assume that it is some kind of security mechanism to prevent something bad.

While this is good, it does not allow the program to calculate huge numbers. In my program, after the variable x reaches 0, it stops the recursive function. Therefore, 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 any way to fix this obstacle?

Answer 1

As already mentioned, you cannot insert the 100,000 factorial into the 64-bit type, since it takes about 1.5 million bits to represent it. (This is a number with zero values ​​of 25000 at the end.)

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

For as easy as recursion, you can eliminate large stack applications with a recursion tail

Then the code should 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 the stack.

Answer 2

I may be too late, but I will add my advice and solutions. This may help you (and others) another time.
The best solution to stackoverflow is not really using recursion at all:

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

Recursion is actually prohibited during programming due to the time (function calls) and resources (stack) that it consumes. In many cases, recursion can be avoided by using loops and a stack with simple pop / push operations, if necessary to preserve the "current position" (in C ++ you can use vector ). In the case of factorial, the stack is not even needed, but if you iterate through the tree structure of the tree , for example, you will need a stack (depending on the implementation).

Now you have another problem with the int size limit: you cannot go above fac(12) if you are working with 32-bit integers, and not fac(20) for 64-bit integers. This can be solved using external libraries that implement operations for large numbers (for example, the GMP library or Boost.multiprecision like SenselessCoder ). But you can also create your own version of BigInteger -like class from Java and implement basic operations like the ones I have. I only implemented multiplication in my example, but the addition is very 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 basic idea is simple, a BigInt is a large decimal number, cutting the little endian representation into pieces. The length of these parts depends on the base you choose. This will only work if your base is 10 : if you choose 10 as the basis, each part will represent one digit, if you choose 100 (= 10 ^ 2) as the basis, each part will represent two consecutive numbers, starting with end (see little end), if you choose 1000 as the base (10 ^ 3), each part will represent three consecutive digits, ... and so on. Let's say that you have a base of 100, 12765 will be [65, 27, 1] , 1789 will be [89, 17] , 505 will be [5, 5] (= [05.5]), ... with base 1000: 12765 will be [765, 12] , 1789 will be [789, 1] , 505 will be [505] .
Multiplication then is a bit like multiplication on paper, which we learned at school:

• start at the bottom of BigInt
• multiply it by a factor
• the smallest part of this product (= base product module) becomes the corresponding part of the final result
• "large" pieces of this product will be added to the product of the following parts.
• go to step 2 with the next part
• If no pieces are left, add the remaining large pieces of the product of the last BigInt fragment to the final result

For instance:

 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 from 1 to 30, as shown in the code below:

  int main() { cout << endl << "Let 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; } 

he will give the following result:

 Let 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 claim is a long answer. I tried to be as brief as possible, but still be complete. Questions are always welcome.
Good luck

Answer 3

I can offer a couple of things for some of the problems you see.

The problem you are not getting to evaluate each recursive step is that you have a stack overflow . This happens when you use more stack space than you should do. This can be avoided by saving a table of previously calculated values. Please note that this will not help if you immediately want to calculate 100,000 factorials, but if you slowly climb onto it by calculating, for example, 10 !, then 20! etc. you will not have this problem. Another important task is to increase the size of the stack. I saw some comments about this, so I will not mention how to do this.

The next problem that you will encounter is that you cannot imagine the numbers that appear as a result of factorial. This is because your integer size is not enough to represent these numbers. In other words, you are overflowing an integer. For this, as well as above, you can see this: Boost.multiprecision . Boost is a very good library that you can use for such things.