ES6 入门系列 (三) 尾递归
2024-09-08 10:33:50
递归我们不陌生,
那什么是尾递归呢?
为什么要用尾递归呢?
尾递归怎么用呢?
带着这三个问题我们来了解它,
我们知道递归非常耗费内存,一不小心就会发生‘栈溢出’, 相信你一定遇到过这个错误: stack overflow,
尾递归就是用来优化递归的这个问题的。
尾递归的定义: 在函数的最后一步返回自身,也就是显示地return自身就称为尾递归。对于尾递归来说,
由于只存在一个调用帧,所以永远不会发生‘栈溢出’。
我们来举例说明尾递归的好处:
- 比如计算n的阶乘, 我们首先想到找规律, n的阶乘等于n* (n-1)的阶乘
- 找出口1的阶乘等于1
- 然后我们就很自然的用递归写出
function jieCheng(n) {
if (n===1) {
return 1
}
return n * jieCheng(n -1);
}
const result = jieCheng(5); console.log(result); //很自然, so easy有木有,
but, 这样我们每递归一次,上一次的调用记录还保存着, 也就是说我们计算n的阶乘最多要保存n个调用记录,复杂度为O(n).
改成尾递归:
function weiJieCheng(n, total=1) {
if (n === 1) {
return total;
}
return weiJieCheng(n-1, n * total);
} console.log(weiJieCheng(5), 'wei'); //
把中间变量改写成函数的参数, 这样就只保存了一个调用记录,复杂度为O(1)。
再用蹦床函数对尾递归进行优化,把递归执行转换成循环执行:
function trampoline(f) {
while(f && f instanceof Function) {
f = f ();
}
}
trampoline(weiJieCheng(5, 1))
最新文章
- appium 自动化测试之知乎Android客户端
- 烂泥:NFS做存储与KVM集成
- ERROR 1045 (28000): Access denied for user 'root'@'localhost'
- WAMP(Windows+Apache+Mysql+PHP)环境搭建
- codeforces55D数位dp
- MVC源码解析 - 目录
- Bitmap与Matrix旋转ImageView
- Django使用遇到的各种问题及解决方法
- 原生Js写轮播图代码
- log4j警告:WARN Please initialize the log4j system properly 的解决方法
- Mysql 常用SQL语句集锦
- 1.python函数式编程-map函数
- MySQL分布式实现ID自增
- Android Dagger 2 无法自动生成 Dagger Component
- getImplementationVersion-获取版本号
- modelsim仿真中遇到的问题
- jre安装配置!
- OpenSSL 中 RSA 加密解密实现源代码分析
- java实际项目中interface和abstract interface 区别
- Android签名生成和互转
热门文章
- 【比赛游记】CSP2019游记
- 201871010106-丁宣元 《面向对象程序设计(java)》第十一周学习总结
- 201871010108-高文利《面向对象程序设计(java)》第六七周学习总结
- 【我的第一个现实漏洞分析】 CVE-2017-17215 华为智能路由器HG532 漏洞分析笔记
- (day45)JavaScript
- shell的变量以及常见符号
- Linux学习笔记-第8天 - 看似很简单
- tornado内置接口调用顺序initialize\prepare...
- 为什么accpet会重新返回一个套接字
- Function.prototype.call.bind