javascript - 关于尾递归的问题
黄舟
黄舟 2017-04-10 15:10:06
[JavaScript讨论组]

引子

mn 为正整数,

  • 当乘积 mn 等于 0 时,函数f(m, n) 等于 m + n + 1
  • 否则 f(m, n) 等于 f(m - 1, f(m, n - 1))

下面是上述问题的一段简单代码(Javascript

javascriptfunction f(m, n) {
    if (m * n == 0) {
        return m + n + 1
    }
    return f(m - 1, f(m , n - 1))
}

console.log(f(2, 1)) // 5

疑惑

摘自电子书ECMA6 入门中的 尾递归 的定义:

函数调用自身,称为递归。如果尾调用自身,就称为尾递归。

引子代码中的函数freturn了自身,但是其第二个参数又调用f,那么在这种情况下,

  1. 函数f算不算是尾递归呢?
  2. 如果f不是尾递归,又如何改成尾递归(如能改)?
黄舟
黄舟

人生最曼妙的风景,竟是内心的淡定与从容!

全部回复(3)
伊谢尔伦

不是尾递归。。 f(m , n - 1)执行结束后需要向上层返回执行结果,也就是把结果给f(m - 1, f(m, n - 1))然后继续递归。。那么程序运行时必然会保存f函数上一层的状态,所以这跟普通递归一样的

阿神

题目里面的不是尾递归,因为函数的最后实际相当于如下形式,很显然不是尾递归。

var r = f(m , n - 1);
return f(m - 1, r);

而把这个函数改造成尾递归是可行的,实际上任何函数都可以改造成尾递归形式。

function f(m, n) {
    function cps(m, n, cb) {
        if (m*n == 0) {
            cb(m + n + 1)
            return
        }

        cps(m, n - 1, function(r) {
            cps(m - 1, r, cb)
        })
    }

    var result
    cps(m, n, function(r) {
        result = r
    })
    return result
}

不过可惜的是,javascript 不支持尾递归优化,改成这种形式之后反而因为增加了中间层次导致挂的更快,所以这个变换在 javascript 里面也只有理论意义而已。

黄舟

當且僅當尾調用自身。

return f(m - 1, f(m , n - 1)) 中的 f(m , n - 1) 顯然不是尾調用。

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号