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

给定一个大数 N ，任务是使用递归查找 N 的阶乘。

非负整数的阶乘是所有小于或等于n的整数的乘积。例如6的阶乘为65432*1，即720。

例子：

输入： N = 100

输出： 933262154439441526816992388562667004-907159682643816214685929638952175999-932299156089414639761565182862536979-208272237582511852109168640000000000-00000000000000

输入： N = 50

输出： 3041409320171337804361260816606476884-4377641568960512000000000000

迭代方法： 迭代方法在本文第一部分进行了讨论。这里，我们讨论递归方法。

递归方法： 为了递归地解决这个问题，算法在调用相同的函数递归地乘以数字n的结果时改变了方式。 请按照以下步骤解决该问题：

• 如果 n 小于等于 2 ，则将 n 乘以 1 并将结果存储在向量中。
• 否则， 调用函数 multiply(n, factorialRecursiveAlgorithm(n – 1)) 查找答案。

下面是以上方法的实现。

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// MUltiply the number x with the number
// represented by res array
vector<int> multiply(long int n, vector<int> digits)
{
  
    // Initialize carry
    long int carry = 0;
  
    // One by one multiply n with
    // individual digits of res[]
    for (long int i = 0; i < digits.size(); i++) {
        long int result 
          = digits[i] * n + carry;
  
        // Store last digit of 'prod' in res[]
        digits[i] = result % 10;
  
        // Put rest in carry
        carry = result / 10;
    }
  
    // Put carry in res and increase result size
    while (carry) {
        digits.push_back(carry % 10);
        carry = carry / 10;
    }
  
    return digits;
}
  
// Function to recursively calculate the
// factorial of a large number
vector<int> factorialRecursiveAlgorithm(
  long int n)
{
    if (n <= 2) {
        return multiply(n, { 1 });
    }
  
    return multiply(
      n, factorialRecursiveAlgorithm(n - 1));
}
  
// Driver Code
int main()
{
    long int n = 50;
  
    vector<int> result 
      =factorialRecursiveAlgorithm(n);
  
    for (long int i = result.size() - 1; i >= 0; i--) {
        cout << result[i];
    }
  
    cout << "\n";
  
    return 0;
}  

输出

30414093201713378043612608166064768844377641568960512000000000000

时间复杂度： O(n)

辅助空间： O(K)，其中K是 输出 中包含的最大数字数量。