javascript递归和尾递归

一、递归 ，即一个函数内部不断循环调用自身函数，需要终止条件。

// 一个累加的递归函数
var s = new Date().getTime()
function count(num){
   if(num<=0){
       return num
   }
   return num + count(num-1)
}
console.log( count(5) );//输出15
var e = new Date().getTime()
console.log('执行时间', e-s)

• 注意：此种递归方式会不断的把函数压入栈，如果num的数值越大，栈就会越大。

二、尾递归，只存在一个函数在栈中。

// 一个累加的递归函数
var s = new Date().getTime()
function count(num, addNum){
   addNum = addNum || 0
   if(num<=0){
       return addNum
   }
   return count( num-1, addNum+num )
}
console.log( count(5) );//输出15
var e = new Date().getTime()
console.log('执行时间', e-s)

三、尾递归优化，栈+循环通用函数（并不是所有环境都支持尾递归）

var s = new Date().getTime()
function tailRecursion(fn){
    var value
    var active = false
    var arr = []
    return function handle(){
        arr.push(arguments)
        if(!active){
            active = true
            while(arr.length){
                value = fn.apply(this, arr.shift())
            }
            active = false
            return value
        }
    }
}
var count = tailRecursion( function(num, addNum){
   addNum = addNum || 0
   if(num<=0){
       return addNum
   }
   return count( num-1, addNum+num )
} )
console.log( count(5) );//输出15
var e = new Date().getTime()
console.log('执行时间', e-s)

四、总结

• 普通递归和尾递归都有栈溢出风险，当我们把count(5)，改成count(100000) 时就会报错

Uncaught RangeError: Maximum call stack size exceeded

• 尾递归栈+循环优化函数执行count(100000)并不会报错，但是相比前两种递归执行时间要更长。
• 尾递归函数作为tailRecursion的参数fn结果输出为15

注意：普通递归函数作为tailRecursion的参数fn结果输出为0