C++ 程序使用递归查找大数的阶乘

阶乘是一个常见的数学运算，即n的阶乘为n*(n-1)*(n-2)*...*3*2*1。但当n较大时，一些编程语言的数据类型无法存储其值。因此，本文将介绍使用递归算法查找大数的阶乘的C++程序。

递归算法

递归是一个常见的程序设计思想，可以简化代码并提高程序的可读性。在数学中，递归定义是一种通过基础情况和递归关系来定义对象或函数的方法。在此处，我们使用递归算法来查找n的阶乘。

阶乘的递归关系为：n! = (n-1)! * n，其中(n-1)!是递归调用的结果。因此，我们可以写出递归函数factorial，如下所示（C++代码）：

unsigned long long factorial(unsigned long long n) {
    if (n == 0) {   // 基础情况
        return 1;
    } else {        // 递归调用
        return n * factorial(n - 1);
    }
}

在这个函数中，如果n等于0，则返回1。否则，返回n乘以递归调用factorial(n-1)的结果。这就是递归算法的基本思想。

请注意，由于阶乘的结果很快变得非常大，所以我们必须使用一个 unsigned long long 或更大的类型（例如 __int128）来存储它们。

示例

让我们使用上面的函数来计算10的阶乘：

#include <iostream>

int main() {
    unsigned long long result = factorial(10);
    std::cout << "10! = " << result << std::endl;
    return 0;
}

这将输出：10! = 3628800。

现在，让我们尝试计算50的阶乘：

#include <iostream>

int main() {
    unsigned long long result = factorial(50);
    std::cout << "50! = " << result << std::endl;
    return 0;
}

不幸的是，这个程序在我的机器上崩溃了，因为超出了unsigned long long的范围。这就是我们需要使用递归算法解决该问题的原因。

现在，让我们使用递归函数来计算50的阶乘：

#include <iostream>

unsigned long long factorial(unsigned long long n);

int main() {
    unsigned long long result = factorial(50);
    std::cout << "50! = " << result << std::endl;
    return 0;
}

unsigned long long factorial(unsigned long long n) {
    if (n == 0) {   // 基础情况
        return 1;
    } else {        // 递归调用
        return n * factorial(n - 1);
    }
}

这会输出：50! = 30414093201713378043612608166064768844377641568960512000000000000。我们成功地计算了50的阶乘！