递归过程中到底发生了什么？

Question

谁能告诉我递归程序中到底发生了什么..？

Answer 1

与迭代相反，递归是一种算法或函数设计，其中函数调用自身。这可以使函数更容易理解，但也会使其变慢，因为必须创建一个新的堆栈。此外，堆栈内存使用量将随着每次调用而线性增加。

另一方面，迭代在一个函数中循环遍历所有内容，将时间复杂度保持在 O(n)，并且空间复杂度固定并且不会随着每次迭代而增加。

例如，考虑一个将连续数字相加的函数。请注意，有一个公式可以通过一个简单的计算（时间复杂度为 O(1)）来完成此操作，但我们仅以此为例。

递归函数可能如下所示：

long consecutive(long a) {
    return a > 1 ? a + consecutive(a - 1) : a + 1;
}

通过此递归调用，您可能很快就会耗尽堆栈内存。然而，迭代模型对此更好：

long consecutive(long a) {
    long result = 0, i;
    for (i = 1; i <= a; i++) result += i;
    return result;
}

Answer 2

递归程序可能如下所示：

def f(i):
    if i > 100:
        return 100
    else:
        return f(i+1)

print f(7)

(python)

问题是，会发生什么？答案是最好从函数的角度来思考这个问题并尝试将它们写出来。

因此，我们有语句 print f(7)。为了找出它的计算结果，我们通过该函数运行 7 并发现它的计算结果为 f(8)。好的，很好，但是它的评估结果是什么？ f(9)。我故意在这里有一个 exit 子句 - 最终 i 在循环中将等于 100，这将是返回的值。会发生什么：

• f(7) = ?
• f(7) = f(8) = ?
• f(7) = f(8) = f(9 ) = ?
• f(7) = f(8) = f(9) = f(10) = ?
• ...
• f( 7) = f(8) = ... = 100
• 所以 f(7) 是 100

这是一个相当简单的示例，但确实很好地演示了递归。

Answer 3

递归示例：

function foo(doRecurse)
{
    alert("Foo was called");

    if (doRecurse)
    {
        foo(false);
    }
}

foo(true);

在此示例中，当 foo 被以 true 调用时，它会再次以 false 调用自身。因此，您将收到两条带有上述代码的警报消息。函数foo调用函数foo的地方就是递归。

Answer 4

正如其他人提到的，递归只是一个调用自身的方法。这有几个优点，但也有一些缺点。

作为示例，阶乘的典型计算：

迭代版本：

int factorial(int factor)
{
    int result = 1;
    int current_factor = 1;
    while (current_factor < factor)
    {
      result *= current_factor;
      ++current_factor;
    }
    return result;
}

递归版本：

int factorial(int factor)
{
  if (factor == 1) return 1;
  return factor * factorial(factor - 1);
}

正如您所看到的，代码更短并且更容易阅读（如果您习惯递归）。

现在让我们检查堆栈：

• 交互版本：3 个整数变量（因子、当前因子、结果）
• 递归版本：
  1:1 变量的阶乘（因子）
  2 的阶乘：2 个变量（因子和阶乘的返回值(因子 - 1)）
  3 的阶乘：3 个变量（因子，阶乘（因子 -1）的返回值，它具有另一个阶乘（因子 - 1）的返回值）
  ...

它看起来大致像这样

factorial(5):
  factorial(4):
    factorial(3):
      factorial(2):
        factorial(1):
        1
      2+1
    3+2+1
  4+3+2+1
5+4+3+2+1

正如你所看到的，递归需要更多的堆栈空间（你必须添加返回指针、变量的压入和弹出以及函数调用所需的其他一些东西）并且通常会更慢。空间问题可以通过使用尾部优化递归来减少，但这对这篇文章来说太大了，但为了完整性，优化版本将如下所示：

int factorial(int current, int end, int *result) // result is a pointer, so changes
                                               // on result affect the original variable
{
  if (current > end) return;
  *result = *result * current;
  factorial(current + 1, end, result);
}

递归真正有用的唯一地方是（恕我直言）遍历树结构。

Answer 5

函数调用自身。这可以用来代替迭代，但通常效率较低，因为必须为每个函数调用分配新的堆栈。

Answer 6

函数会一遍又一遍地调用自身，直到满足某些条件。

一个愚蠢的例子：如何递归地走 100 步：

 function walk(steps) {
     if (steps > 0) { // not there yet
        take 1 step
        walk(steps - 1); // we're 1 step closer, now walk the rest of the way
     } else { // we're there already, don't walk any further than requested
        echo "You're there!"
     }
 }

 walk(100); // go!

这就是发生的情况：

 walk(100):
   take 1 step
   walk(99):
     take 1 step
     walk(98):
       take 1 step
       walk(97):
         (...)
                   walk(2):
                     take 1 step
                     walk(1):
                       take 1 step
                       walk(0):
                         // "steps > 0" no longer true, use the "else" branch
                         echo "You're there!"

可以使用循环（“迭代”）完成同样的事情：

function walk(steps) {
  for (c=steps; c > 0; c--) { // note the condition check - "c > 0"
    take 1 step
  }
  echo "You're there!"
}

walk(100); // go!

程序流程会有点不同，但结果是相同的：

walk(100):
  c=100
  take 1 step
  c=99
  take 1 step
  c=98
  take 1 step
  (...)
  c=2
  take 1 step
  c=1
  take 1 step
  c=0
  // "c > 0" no longer true, exit loop
  echo "You're there!"

请注意， 不能说递归和迭代哪个更好。在这个例子中，迭代（循环）比递归写起来更简单，也更容易理解；在其他情况下（例如遍历树结构），递归可能是更好的解决方案。