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

Question

我有一个递归函数的下面的例子，什么我不明白是为了在事情发生：

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

什么时候函数返回的值，在全部过程结束或每次？

Answer 1

一个简单的方法来可视化递归一般发生的事情是这样的：

1. 一个堆栈中创建调用该函数的：这个过程需要一个适当的终止条件来结束（否则你“会具有无限递归，这是恶）
2. 单结果弹出出栈：每个结果被用来计算下一个步骤，直到堆栈为空

即，如果碱= 5和指数= 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 

注意的是，这里的功能的计算方法为在逆顺序为：先power(5, 0)，然后power(5, 1)，等等..每个calulation叠层的元件被释放之后（即，存储器被释放）。

希望它能帮助:)

Answer 2

与任何递归函数一样，当计算返回值时，会从特定“实例”返回。这意味着递归版本将被计算。

因此，如果你传入4的指数，那么在某个时刻将会有4个拷贝的函数被一次执行。

Answer 3

它通常有助于理解递归函数，例如像在代数类中那样工作。试想一下：

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 4

这里的关键是，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。

当试图理解这样的事情时，没有什么比使用调试器遍历代码更好。在这个现代世界，you have plenty to choose from，其中许多可能已经在您的计算机上。

Answer 5

这条线，其分辨率真的绊倒了我，让

return base * power(base, exponent - 1) 

我得到的指数递减，直到它满足了基本情况，但是当你mulitply 的基地时代的递归函数调用，我一直在想“函数如何多重地基于它自己（基本参数）？”，它在那里做的确切，因为调用base * power（base，exponent-1）不看起来像标准循环结构。它如何通过两个论证来调用函数，它如何知道跳过指数论证并将基数乘以基数？

Answer 6

从数学的角度：

设X =碱， 令n =指数

x*x^(n-1) = x^n

因为

x^1*x^n-1=x^n（如术语的指数相加）

它是一样的：

base * base*exponent-1. 

Answer 7

为了更好的可视化，只需将函数调用替换为函数体（例如可能是伪代码）即可。

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

power(5, 3)扩大到这个

function power(5, 3) { 
    // exponent 3 is not 0 

    // return 5 * power(5, 3-1) 
    return 5 * function power(5, 2) { 
     // exponent 2 is not 0 

     // return 5 * power(5, 2-1) 
     return 5 * function power(5, 1) { 
      //exponent 1 is not 0 

      // return 5 * power(5, 1-1) 
      return 5 * function power(5, 0){ 
       //exponent 0 is 0 
       return 1; 
      } 
     } 
    } 
} 

现在画面清晰。它全部变成下面这样..

// 1 
function power(5, 3){ 
    return 5 * function power(5, 2){ 
     return 5 * function power(5, 1){ 
      return 5 * (function power(5, 0){ 
       return 1; 
      }) 
     } 
    } 
} 

// 2 
function power(5, 3){ 
    return 5 * function power(5, 2){ 
     return 5 * (function power(5, 1){ 
      return 5 * 1; 
     }) 
    } 
} 

// 3 
function power(5, 3){ 
    return 5 * (function power(5, 2){ 
     return 5 * 5 * 1; 
    }) 
} 

// 4 
function power(5, 3){ 
    return (5 * 5 * 5 * 1); 
} 

// 5 
5 * 5 * 5 * 1;