在C++中减少递归函数中堆栈的使用

Question

我有一个计算任何数字的阶乘的程序.当我尝试将其作为100,000这样的大数字时,它会在它达到0之前停止.我猜这是一种防止出现问题的安全机制.

虽然这很好,但它可以防止程序计算大量数字.在我的程序中,变量x达到0后,它会停止递归函数.所以不需要这个"安全网".

这是我的代码供参考:

#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";
    }
}

有没有办法解决这个障碍？

Answer 1

正如其他人所提到的，您将无法将阶乘100,000放入 64 位类型中，因为它需要大约 150 万位来表示它。25000（这是一个末尾大约有零的数字。）

然而，假设我们将问题从 改为递归加法[1..100000]。您仍然会遇到堆栈问题。堆栈是有限的，并且递归使用堆栈，因此可以进行的调用数量存在基本限制。

对于像递归这样简单的事情，您可以通过使用尾递归来消除堆栈的大量使用

然后代码需要更改为：

#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
}

在上面的情况下，由于递归后没有其他操作，编译器会进行优化，不会耗尽堆栈。