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