JavaScript 尾递归

■知识点

    尾递归是递归的一种优化算法，它从最后开始计算，每递归一次就算出相应的结果，即函数调用出现在调用函数的尾部，因为是尾部，所以就不用去保存任何局部变量，返回时调用函数可以直接越过调用用者，返回到调用者的调用者。

■实例设计

下面是阶乘的一种普通线性递归运算。

function f( n ){

    return ( n == 1 ) ? l : n * f( n - l );

}

console.log(f (5) ) ;        //120

使用尾递归算法后，则可以使用如下方法。

function f ( n, a ){

    return ( n==l ) ? a : f( n - l, a * n );

}

console.log( f (5 , 1) ); //120

当n = 5时，线性递归的递归过程如下。

f(5) = {5 * f (4) }

     = {5 * {4 * f(3)}}

     = {5 * {4 * {3 * f(2) }}}

     = {5 * {4 * {3 * {2 * f(1) } } } }

     = {5 * {4 * {3 * {2 * 1}}}}

     = {5 * {4 * {3 * 2}}}

     = {5 * {4 * 6}}

     = {5 * 24}

     = 120

而尾递归的递归过程如下。

f(5) = f(5, 1)

     = f(4, 5)

     = f(3, 20)

     = f(2, 60)

     = f(1, 120)

     = 120

从上面的代码中很容易看出，普通递归比尾递归更加消耗资源，每次重复的过程调用都使得调用链条不断加长，系统不得不使用栈进行数据保存和恢复，而尾递归就不存在这样的问题，因为它的状态完全由变量n和a保存。

■小结

    从理论上分析，尾递归也是递归的一种类型，不过它的算法具有迭代算法的特征。上面的阶乘尾递归可以改写为下面的迭代循环。

var n = 5 

var w = 1;

for ( var i = 1; i <= 5; i ++ ) {

    w = w * i;

}

console.log ( w );

尾递归由于直接返回值，不需要保存临时变量，所以性能不会产生线性增加，同时JavaScript引擎会将尾递归形式优化成非递归形式。