尾递归
2023-09-14 08:58:55 时间
一、什么是尾调用?
尾调用的概念非常简单,一句话就能说清楚,就是指某个函数的最后一步是调用另一个函数。
function f(x){ return g(x); }
二、尾调用优化
函数在调用的时候会在调用栈(call stack)中存有记录,每一条记录叫做一个调用帧(call frame),每调用一个函数,就向栈中push一条记录,函数执行结束后依次向外弹出,直到清空调用栈,参考下图:
function foo () { console.log(111); } function bar () { foo(); } function baz () { bar(); } baz();
造成这种结果是因为每个函数在调用另一个函数的时候,并没有 return 该调用,所以JS引擎会认为你还没有执行完,会保留你的调用帧。
如果对上面的例子做如下修改:
function foo () { console.log(111); } function bar () { return foo(); } function baz () { return bar(); } baz();
二、什么是尾递归?
前面我们知道了尾调用的概念,当一个函数尾调用自身,就叫做尾递归。
function foo () { return foo(); }
那么尾递归相比递归而言,有哪些不同呢?
我们通过下面这个求阶乘的例子来看一下:
function factorial (num) { if (num === 1) return 1; return num * factorial(num - 1); } factorial(5); // 120 factorial(10); // 3628800 factorial(500000); // Uncaught RangeError: Maximum call stack size exceeded
如果用尾递归来计算阶乘呢?
'use strict'; function factorial (num, total) { if (num === 1) return total; return factorial(num - 1, num * total); } factorial(5, 1); // 120 factorial(10, 1); // 3628800 factorial(500000, 1); // 分情况
ps:值得注意的是,虽然说这里启用了严格模式,但是经测试,在Chrome和Firefox下,还是会报栈溢出错误,并没有进行尾调用优化
Safari浏览器进行了尾调用优化,factorial(500000, 1)结果为Infinity,因为结果超出了JS可表示的数字范围
如果在node v6版本下执行,需要加--harmony_tailcalls参数,node --harmony_tailcalls test.js
node最新版本已经移除了--harmony_tailcalls功能
博主试了一下,下面这个函数,最多可以到 12578 次递归
function F(n) { if (n>12577) return n; return F(n+1); }
相关文章
- Java实现 LeetCode 753 破解保险箱(递归)
- 第三百二十六节,web爬虫,scrapy模块,解决重复ur——自动递归url
- 尾递归(转)
- 数据结构和算法学习三,之递归和堆栈
- SQL递归查询实例
- Leetcode0427. 建立四叉树(medium,递归)
- 【数独问题】递归+回溯算法求解数独问题
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-449 递归输出数字三角形
- 通过展开序列ISTA(SISTA)算法创建的递归神经网络(RNN)(Matlab代码实现)
- Java递归构建树形结构
- 779. 第K个语法符号-递归法
- C语言递归求和
- PostgreSQL的学习心得和知识总结(七十四)|深入理解PostgreSQL数据库最新版本14下的可递归公共表达式表CTE功能增强(SEARCH和CYCLE) 原理
- python 实现函数的递归
- 变形二叉树中节点的最大距离(树的最长路径)——非递归解法