javascript - 对这个简单的递归函数如何工作感到非常困惑 - 如何解释它？

Question

我必须创建函数来返回一个指数上升的数字。我用循环解决了它:

function pow(x, n) {
  let result = 1;

  // multiply result by x n times in the loop
  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

我看到另一个使用递归的函数。我知道递归可能涉及函数调用自身，但在这种情况下，结果最终如何添加到“堆栈”并返回正确的答案？无论我如何思考，我都无法理解这个微小的功能是如何工作的。

也许一个简单的类比会有所帮助 - 有什么想法吗？当我尝试在脑海中运行该函数时，这是没有意义的:/

function pow(x, n) {
    if (n == 1) {
      return x;
    } else {
      return x * pow(x, n - 1);
    }
}

alert( pow(2, 3) ); // 8

Answer 1

我们来介绍一些操作。

PUSH X 将把 X 压入堆栈。

MULTIPLY 将从堆栈中弹出 2 个内容，将它们相乘并将结果推回堆栈。

调用一个我们将用一些缩进来描述的函数。

我们将堆栈本身描述为一个像[ A, B, C ]这样的数组，其中C是最后一个被插入堆栈的东西(即:堆栈的“顶部”)。

我将编写指令，然后是执行指令后堆栈的状态:

计算A * B:

堆栈最初是空的[]。

PUSH A   [ A ]
PUSH B   [ A, B ]
MULTIPLY [ A*B ]

这会将 A 和 B 的乘积留在堆栈上。

计算A * (B * C)

PUSH A [A]
PUSH B [A, B]
PUSH C [A, B, C]
MULTIPLY [A, B*C]
MULTIPLY [A*B*C]

现在您已经了解了符号，让我们看看如何计算 pow(2,3)

我会写 ? 表示“我们还不知道，因为我们还没有扩展函数调用的作用。”

PUSH 2 [2]
pow(2,2) [2, ?]
MULTIPLY [2*?]

乘法尚未发生。我们刚刚展望了 future 。注意有一个？在结果中。我们不知道调用 pow(2,2) 时会发生什么，但无论发生什么，我们都会发出一条 MULTIPLY 指令。

现在让我们用 pow(2,2) 实际执行的操作来扩展时间线:

PUSH 2 [2]
  PUSH 2 [2, 2]
  pow(2,1) [2, 2, ?]
  MULTIPLY [2, 2*?]
MULTIPLY [2*2*?]

请注意，我们还没有完全完成扩展。我们实际上并没有深入研究 pow(2,1) 做了什么，但我们只是压入 2，在调用完成后，我们将发出 MULTIPLY 指令再次。

现在让我们最终扩展一下 pow(2,1) 的功能。它只是推送一个值 - 不再进行任何函数调用:

PUSH 2 [2]
  PUSH 2 [2, 2]
    PUSH 2 [2, 2, 2]
  MULTIPLY [2, 2*2]
MULTIPLY [2*2*2]

如果您只是去掉缩进并计算表达式，剩下的就是它如何使用堆栈计算值的记录。

PUSH 2 [2]
PUSH 2 [2, 2]
PUSH 2 [2, 2, 2]
MULTIPLY [2, 4]
MULTIPLY [8]

请注意，一般来说，对于 pow(x,n) ，机器将执行 PUSH X n 次，然后执行 >MULTIPLY n - 1 次。