首页 >> js开发 >> jses6函数之尾递归用法实例分析js大全
jses6函数之尾递归用法实例分析js大全
发布时间: 2021年1月13日 | 浏览:
| 分类:js开发
本文实例讲述了es6函数之尾递归用法。分享给大家供大家参考,具体如下:函数调用自身,称为递归,如果尾调用自身,就称为尾递归。递归非常耗费内存。因为需要同时保存成千上百个调用帧,很容易发生“栈溢出”错误(stack overflow)。但是对于尾递归来说,由于只存在一个调用帧,所以永远不会发生“栈溢出”错误。
function factorial(n) {
if (n === 1) return 1
return n * factorial(n - 1)
}
function factorial(n) {
if (n === 1) return 1
return n * factorial(n - 1)
}
如果改成尾递归,只保留一个调用记录,复杂度O(1)
function factorial(n, total = 1) {
if (n === 1) return total
return factorial(n - 1, n * total)
}
factorial(5)
function factorial(n, total = 1) {
if (n === 1) return total
return factorial(n - 1, n * total)
}
factorial(5)
非尾递归的 Fibonacci 数列实现如下。
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) // 堆栈溢出
Fibonacci(500) // 堆栈溢出
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) // 堆栈溢出
Fibonacci(500) // 堆栈溢出
尾递归优化过的 Fibonacci 数列实现如下。
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
尾递归的实现,往往需要改写递归函数,确保最后一步只调用自身。做到这一点的方法,就是把所有用到的内部变量改写成函数的参数。函数式编程有一个概念,叫做柯里化(currying),意思是将多参数的函数转换成单参数的形式。这里可以使用柯里化。
function currying(fn, n) {
return function(m) {
return fn.call(this, m, n)
}
}
function currying(fn, n) {
return function(m) {
return fn.call(this, m, n)
}
}
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools./code/HtmlJsRun测试上述代码运行效果。在线HTML/CSS/JavaScript代码运行工具在线HTML/CSS/JavaScript代码运行工具http://tools./code/HtmlJsRun关于JavaScript相关内容可查看本站专题:《JavaScript常用函数技巧汇总》、《javascript面向对象入门教程》、《JavaScript错误与调试技巧总结》、《JavaScript数据结构与算法技巧总结》及《JavaScript数学运算用法总结》JavaScript常用函数技巧汇总javascript面向对象入门教程JavaScript错误与调试技巧总结JavaScript数据结构与算法技巧总结JavaScript数学运算用法总结希望本文所述对大家JavaScript程序设计有所帮助。
function factorial(n) {
if (n === 1) return 1
return n * factorial(n - 1)
}
function factorial(n) {
if (n === 1) return 1
return n * factorial(n - 1)
}
如果改成尾递归,只保留一个调用记录,复杂度O(1)
function factorial(n, total = 1) {
if (n === 1) return total
return factorial(n - 1, n * total)
}
factorial(5)
function factorial(n, total = 1) {
if (n === 1) return total
return factorial(n - 1, n * total)
}
factorial(5)
非尾递归的 Fibonacci 数列实现如下。
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) // 堆栈溢出
Fibonacci(500) // 堆栈溢出
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) // 堆栈溢出
Fibonacci(500) // 堆栈溢出
尾递归优化过的 Fibonacci 数列实现如下。
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
尾递归的实现,往往需要改写递归函数,确保最后一步只调用自身。做到这一点的方法,就是把所有用到的内部变量改写成函数的参数。函数式编程有一个概念,叫做柯里化(currying),意思是将多参数的函数转换成单参数的形式。这里可以使用柯里化。
function currying(fn, n) {
return function(m) {
return fn.call(this, m, n)
}
}
function currying(fn, n) {
return function(m) {
return fn.call(this, m, n)
}
}
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools./code/HtmlJsRun测试上述代码运行效果。在线HTML/CSS/JavaScript代码运行工具在线HTML/CSS/JavaScript代码运行工具http://tools./code/HtmlJsRun关于JavaScript相关内容可查看本站专题:《JavaScript常用函数技巧汇总》、《javascript面向对象入门教程》、《JavaScript错误与调试技巧总结》、《JavaScript数据结构与算法技巧总结》及《JavaScript数学运算用法总结》JavaScript常用函数技巧汇总javascript面向对象入门教程JavaScript错误与调试技巧总结JavaScript数据结构与算法技巧总结JavaScript数学运算用法总结希望本文所述对大家JavaScript程序设计有所帮助。
相关文章:
- js代码全面解析JavaScript Module模式
- js解决vue 使用setTimeout,离开当前路由setTimeout未销毁的问题js大全
- jsvue element 关闭当前tab 跳转到上一路由操作js大全
- jsvue项目中使用多选框的实例代码js大全
- js基于 Vue 的 Electron 项目搭建过程图文详解js大全
- js浅谈JS for循环中使用break和continue的区别js大全
- js详谈vue中router-link和传统a链接的区别js大全
- js详解vue中v-on事件监听指令的基本用法js大全
- jsvue移动端弹起蒙层滑动禁止底部滑动操作js大全
- js解决vue单页面 回退页面 keeplive 缓存问题js大全