这个递归函数究竟是如何在JavaScript中运行的？

Question

我有一个递归函数的例子,我不明白的是事情发生的顺序:

function power(base, exponent) {
  if (exponent == 0)
    return 1;
  else
    return base * power(base, exponent - 1);
}

函数何时返回值,在所有过程结束时或每次？

Answer 1

一般来说,一种简单的方法可视化递归中发生的事情:

1. 一个堆栈中创建调用函数:这个过程需要一个适当的终止条件来结束(否则你就会有无限递归,这是邪恶的)
2. 单个结果从堆栈中弹出:每个结果用于计算下一步,直到堆栈为空

即如果base = 5且exponent = 3,则调用堆栈是(最后一个元素在顶部):

5*(5*(5*1))
5*(5*(5*power(5, 0)))
5*(5*power(5, 1))
5*power(5, 2)
power(5, 3)

然后每个被调用的函数都有实参,并准备返回一个值(顶部的第一个元素):

5*(5*(5*1))
5*(5*5)
5*25
125

注意,这里的函数按相反顺序计算:first power(5, 0),then power(5, 1),依此类推.在每次计算之后,释放堆栈的一个元素(即释放内存).

希望能帮助到你 :)

Answer 2

它通常有助于理解像这样的递归函数,就像在代数类中一样.考虑:

power(3, 4) 
= 3 * power(3, 3)
= 3 * (3 * power(3, 2))
= 3 * (3 * (3 * power(3, 1)))
= 3 * (3 * (3 * (3 * power(3, 0))))
= 3 * (3 * (3 * (3 * 1)))
= 3 * (3 * (3 * 3))
...
= 81

Answer 3

这里的关键power是调用自己完全可以调用任何其他函数的方式.因此,当它这样做时,它等待函数返回并使用其返回值.

所以,如果你这样做

var x = power(10, 2);

1. 您的来电power将到达此行:

   return base * power(base, exponent - 1)
   

   ......并打电话power(10, 1),等待返回.

2. power(10, 1)当然,对意志的呼唤是这样的:

   return base * power(base, exponent - 1)
   

   ......并打电话power(10, 0),等待返回.

3. power(10, 0)将返回的呼叫1,然后由上面#2中的呼叫用于完成其工作并返回10 * 1= 10,这将使您在上面的#1中的原始呼叫返回值10 * 10= 100.

在寻求理解这样的事情时,没有什么比使用调试器遍历代码更好的了.在这个现代世界中,您有很多选择,其中许多可能已经在您的计算机上.