使用递归函数是否可能导致堆栈溢出？

Question

这个功能有问题吗？

 unsigned long factorial(unsigned long m)
 {
     return (m == 0) ? 1 : m * factorial(m - 1);
 }

如果我添加另一个函数：

  int myCombina(int q, int p)
  {
      return factorial(q) / ( factorial(q) * factorial(q-p) );
  }

这个 myCombina() 效率不高，因为应该取消其中的最大公约数才能找到组合。

max(阶乘(q),阶乘(qp))可以被取消。 我们只需要计算 qx (q-1) ... x (q -k +1)。

还有其他问题吗？

欢迎任何评论。

谢谢

Answer 1

如果m很大，可能会出现堆栈溢出。

堆栈溢出不是代码的主要问题...如果 m 非常大，您将得到 整数溢出 在出现堆栈溢出之前。

如果您希望它适用于大于 12 的 m（取决于您平台上的 unsigned long 的大小），您需要使用某种 Bignum 类型。

Answer 2

它不是以尾递归形式编写的，因此即使编译器支持适当的尾调用优化，您也不会受益。

Answer 3

该函数实际上可能会导致堆栈溢出（每个递归级别都会消耗一点堆栈，直到全部消耗完为止）。

正如其他人提到的，您可以将递归函数转换为循环，在本例中这很简单，或者您可以修改递归以允许尾部调用优化（让编译器将递归转换为循环）。

正因为如此，要转变为尾递归调用，函数的最后一条语句必须是返回递归调用得到的结果。您的代码无法被优化掉，因为您的 return 语句包含 m*factorial(n-1)，也就是说，您不返回递归的值，而是在返回之前对其进行实际操作。

使其尾递归的转换需要将乘法下推到递归调用，这通常作为保留临时结果的额外参数执行：

unsigned long factorial_tail_recursive( 
                        unsigned long n,           // number to calculate factorial
                        unsigned long temp_result  // accumulated result
                      ) 
{
   return n == 0? tmp_result 
                : factorial_tail_recursive( n-1, n*temp_result );
}

// syntactic sugar to offer the same interface
unsigned long factorial( unsigned long n ) {
   return factorial_tail_recursive( n, 1 );    // accumulated result initialized to 1
}

但话又说回来，对于该特定问题，有效的迭代解决方案可能更容易得到正确的结果。只需将累积结果保存在临时变量中并循环，直到参数减少到 1。