减少 C++ 递归函数中堆栈的使用
Reducing usage of stack in recursive function in C++
我有一个程序可以计算任何数字的阶乘。当我尝试对一个大数字（例如 100,000）执行此操作时，它会在达到 0 之前停止。我猜这是某种防止不良事件发生的安全机制。
虽然这很好，但它会阻止程序计算巨大的数字。在我的程序中，变量 x 达到 0 后，它停止递归函数。所以不需要这个"safety net".
这是我的参考代码：
#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";
}
}
有没有办法解决这个障碍？
我可以针对您遇到的一些问题提出一些建议。
您无法评估每个递归步骤的问题是因为您遇到了堆栈溢出。当使用比您更多的堆栈space时会发生这种情况。重新打算做。您可以通过保留先前计算的值的 table 来避免这种情况。请注意，如果您立即想计算 100000 的阶乘，这将无济于事，但如果您通过计算慢慢爬升到那个值，例如 10!，然后 20!等你不会有这个问题。要做的另一件事是增加筹码量。看到一些评论，就不说了。
您将 运行 遇到的下一个问题是您将无法表示作为阶乘结果的数字。这是因为您的整数大小不足以表示这些数字。换句话说，你溢出了整数。对于这一点，还有上面的一点，你可以看到这个：Boost.multiprecision。 Boost 是一个非常好的库，你可以用它来做这样的事情。
正如其他人所提到的，您将无法将 100,000 的阶乘放入 64 位类型中，因为它需要大约 150 万位来表示它。 （这是一个末尾有大约 25000 个零的数字。）
但是，假设我们将问题从 [1..100000] 改为递归加法。您仍然会遇到堆栈问题。堆栈是有限的，递归使用堆栈，因此您可以进行的调用次数有一个基本限制。
对于像递归这样简单的事情，您可以通过使用 tail recursion
来消除堆栈的大量使用
然后需要将代码更改为：
#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
}
在上面的例子中，由于递归后没有其他操作，编译器会优化，不会用完栈。
也许我来晚了一点，但我仍然会添加我的建议和解决方案。它可能会在下次帮助您（和其他人）。
解决Whosebug问题最好的办法其实就是根本不用递归：
int fac(int n){
int res=1;
for(int i = 0; i <= n; ++i){
res *= i;
}
return res;
}
递归实际上在编程时被取消，因为它消耗时间（函数调用）和资源（堆栈）。在许多情况下，如果需要保存 "current position"（在 C++ 中可以使用 vector），可以通过使用循环和具有简单 pop/push 操作的堆栈来避免递归。在阶乘的情况下，甚至不需要堆栈，但是如果您要遍历 tree datastructure，例如您将需要一个堆栈（尽管取决于实现）。
现在您遇到的另一个问题是 int 大小的限制：如果您使用 32 位整数并且不超过 [=18]，则不能超过 fac(12) =] 用于 64 位整数。这可以通过使用实现大数字操作的外部库来解决（比如 Java 中的 GMP library or Boost.multiprecision as mentionned). But you could also create your own version of a BigInteger-like class 并实现像我所拥有的那样的基本操作。我只有在我的示例中实现了乘法，但加法非常相似：
#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]);
}
}
主要思想很简单，BigInt通过将其little endian表示分割成碎片来表示一个大的十进制数。这些片段的长度取决于您选择的底座。 只有当你的基数是 10 的幂时才有效：如果你选择 10 作为基数，每块代表一个数字，如果你选择 100 (= 10^2) 作为基数，每块代表一个数字将代表从末尾开始的两个连续数字（请参阅小端），如果您选择 1000 作为基数 (10^3)，则每个部分将代表三个连续数字，...等等。假设您的基数为 100，那么 12765 将是 [65, 27, 1]，1789 将是 [89, 17]，505 将是 [5, 5]（= [05,5]），...基数为 1000 : 12765 将是 [765, 12]，1789 将是 [789, 1]，505 将是 [505].
那么乘法有点像我们在学校学的纸上乘法：
- 从
BigInt 的最低部分开始
- 乘以乘数
- 该产品的最低部分（=产品模数基数）成为最终结果的相应部分
- 该产品的 "bigger" 件将添加到以下件的产品中
- 进入下一个步骤 2
- 如果没有剩余，则将
BigInt最后一块产品的剩余较大块添加到最终结果
例如：
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
如果我使用上面的 class 来计算 1 到 30 之间所有数字的阶乘，如下面的代码所示：
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;
}
它将给出以下结果：
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
我很抱歉回答很长。我试图尽可能简短，但仍然完整。欢迎提问
祝你好运！
我有一个程序可以计算任何数字的阶乘。当我尝试对一个大数字（例如 100,000）执行此操作时，它会在达到 0 之前停止。我猜这是某种防止不良事件发生的安全机制。
虽然这很好，但它会阻止程序计算巨大的数字。在我的程序中，变量 x 达到 0 后，它停止递归函数。所以不需要这个"safety net".
这是我的参考代码：
#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";
}
}
有没有办法解决这个障碍？
我可以针对您遇到的一些问题提出一些建议。
您无法评估每个递归步骤的问题是因为您遇到了堆栈溢出。当使用比您更多的堆栈space时会发生这种情况。重新打算做。您可以通过保留先前计算的值的 table 来避免这种情况。请注意，如果您立即想计算 100000 的阶乘，这将无济于事，但如果您通过计算慢慢爬升到那个值，例如 10!，然后 20!等你不会有这个问题。要做的另一件事是增加筹码量。看到一些评论，就不说了。
您将 运行 遇到的下一个问题是您将无法表示作为阶乘结果的数字。这是因为您的整数大小不足以表示这些数字。换句话说，你溢出了整数。对于这一点，还有上面的一点，你可以看到这个：Boost.multiprecision。 Boost 是一个非常好的库，你可以用它来做这样的事情。
正如其他人所提到的，您将无法将 100,000 的阶乘放入 64 位类型中，因为它需要大约 150 万位来表示它。 （这是一个末尾有大约 25000 个零的数字。）
但是，假设我们将问题从 [1..100000] 改为递归加法。您仍然会遇到堆栈问题。堆栈是有限的，递归使用堆栈，因此您可以进行的调用次数有一个基本限制。
对于像递归这样简单的事情，您可以通过使用 tail recursion
来消除堆栈的大量使用然后需要将代码更改为：
#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
}
在上面的例子中，由于递归后没有其他操作，编译器会优化，不会用完栈。
也许我来晚了一点，但我仍然会添加我的建议和解决方案。它可能会在下次帮助您（和其他人）。
解决Whosebug问题最好的办法其实就是根本不用递归：
int fac(int n){
int res=1;
for(int i = 0; i <= n; ++i){
res *= i;
}
return res;
}
递归实际上在编程时被取消，因为它消耗时间（函数调用）和资源（堆栈）。在许多情况下，如果需要保存 "current position"（在 C++ 中可以使用 vector），可以通过使用循环和具有简单 pop/push 操作的堆栈来避免递归。在阶乘的情况下，甚至不需要堆栈，但是如果您要遍历 tree datastructure，例如您将需要一个堆栈（尽管取决于实现）。
现在您遇到的另一个问题是 int 大小的限制：如果您使用 32 位整数并且不超过 [=18]，则不能超过 fac(12) =] 用于 64 位整数。这可以通过使用实现大数字操作的外部库来解决（比如 Java 中的 GMP library or Boost.multiprecision as BigInteger-like class 并实现像我所拥有的那样的基本操作。我只有在我的示例中实现了乘法，但加法非常相似：
#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]);
}
}
主要思想很简单，BigInt通过将其little endian表示分割成碎片来表示一个大的十进制数。这些片段的长度取决于您选择的底座。 只有当你的基数是 10 的幂时才有效：如果你选择 10 作为基数，每块代表一个数字，如果你选择 100 (= 10^2) 作为基数，每块代表一个数字将代表从末尾开始的两个连续数字（请参阅小端），如果您选择 1000 作为基数 (10^3)，则每个部分将代表三个连续数字，...等等。假设您的基数为 100，那么 12765 将是 [65, 27, 1]，1789 将是 [89, 17]，505 将是 [5, 5]（= [05,5]），...基数为 1000 : 12765 将是 [765, 12]，1789 将是 [789, 1]，505 将是 [505].
那么乘法有点像我们在学校学的纸上乘法：
- 从
BigInt 的最低部分开始
- 乘以乘数
- 该产品的最低部分（=产品模数基数）成为最终结果的相应部分
- 该产品的 "bigger" 件将添加到以下件的产品中
- 进入下一个步骤 2
- 如果没有剩余，则将
BigInt最后一块产品的剩余较大块添加到最终结果
例如：
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
如果我使用上面的 class 来计算 1 到 30 之间所有数字的阶乘，如下面的代码所示：
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;
}
它将给出以下结果：
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
我很抱歉回答很长。我试图尽可能简短，但仍然完整。欢迎提问
祝你好运！