language-agnostic - 递归如何使运行时内存的使用不可预测？

Question

引用Code Complete 2，

int Factorial( int number ) {
   if ( number == 1 ) {
      return 1;
   }
   else {
      return number * Factorial( number - 1 );
   }
}

除了速度慢^[1]和 运行时内存的使用不可预测^[2]之外，此例程的递归版本比迭代版本更难理解，如下所示：

int Factorial( int number ) {
   int intermediateResult = 1;
   for ( int factor = 2; factor <= number; factor++ ) {
      intermediateResult = intermediateResult * factor;
   }
   return intermediateResult;
}

我认为缓慢的部分是因为不必要的函数调用开销。

但是递归如何使运行时内存的使用变得不可预测？

我们不能总是预测需要多少内存（因为我们知道递归应该何时结束）？我认为这将与迭代案例一样不可预测，但不再如此。

Answer 1

由于递归方法反复调用它们自身，需要大量的堆栈内存。由于堆栈是有限的，如果超出堆栈内存就会发生错误。

Answer 2

我们不能总是预测需要多少内存（因为我们知道递归应该何时结束）？我认为这将与迭代案例一样不可预测，但不再如此。

不，不是在一般情况下。有关更多背景信息，请参阅有关停止问题的讨论。现在，这是那里发布的问题之一的递归版本：

void u(int x) {
    if (x != 1) {
        u((x % 2 == 0) ? x/2 : 3*x+1);
    }
}

It's even tail-recursive. Since you can't predict if this will even terminate normally, how can you predict how much memory is needed?

Answer 3

如果递归级别变得太深，您将破坏调用堆栈并在此过程中占用大量内存。如果您number的值“足够大”，则可能会发生这种情况。你能做得比这更糟吗？是的，如果您的函数在每次递归调用时分配更多对象。