迎接ECMAScript 6, 使用尾递归

whatsns 发布于2019-08-21 10:21 / 1654人阅读

摘要：而且最的是，在，我们将迎来尾递归优化，享受只有这些古典函数式语言才拥有的能力。使用尾递归这里有一个使用尾递归提取绝对文件名的例子，可以来展示下尾递归的魅力。

尾调用，是指函数内部的最后一个动作是函数调用。该调用的返回值，直接返回给函数。

Example:

function sum(x) {
    return sum(x + 1);
}

这里的 sum() 内部的 sum 就是属于尾调用，ta 所返回的值直接返回给调用 ta 的上层 sum() 函数。

function sum(x) {
    return 1 + sum(x + 1);
}

这里的 sum() 内部的 sum 就不属于尾调用，ta 所返回的值在返回给调用 ta 的上层 sum() 函数之前，需要先跟 1 计算和，然后再返回。

尾调用和非尾调用有什么差异？

编写一个求和函数，有大致3种方式:

循环

function sum(x) {
    var result = x;
    while (x >= 1) {
        result += --x;
    }
    return result;
}

循环自然是速度和性能最好的，但是在编写复杂的代码时，循环往往模块化很差，可读性很差，而且无法体现数学上的描述。

普通递归

function sum(x) {
    if (x === 1) {
        return 1;
    }
    return x + sum(--x);
}

普通递归时，内存需要记录调用的堆栈所出的深度和位置信息。在最底层计算返回值，再根据记录的信息，跳回上一层级计算，然后再跳回更高一层，依次运行，直到最外层的调用函数。在cpu计算和内存会消耗很多，而且当深度过大时，会出现堆栈溢出。

比如，计算 sum(5) 的时候，其计算过程是这样的:

sum(5)
(5 + sum(4))
(5 + (4 + sum(3)))
(5 + (4 + (3 + sum(2))))
(5 + (4 + (3 + (2 + sum(1)))))
(5 + (4 + (3 + (2 + 1))))
(5 + (4 + (3 + 3)))
(5 + (4 + 6))
(5 + 10)
15

在计算的过程中，堆栈一直不停的记录每一层次的详细信息，以确保该层次的操作完成，能返回到上一层次。

通过尾递归，可以取消过多的堆栈记录，而只记录最外层和当前层的信息，完成计算后，立刻返回到最上层。从而减少 cpu 计算和内存消耗。

尾递归

function sum(x, total) {
    if (x === 1) {
        return x + total;
    }
    return sum(--x, x + total);
}

这个函数更具有数学描述性:

如果输入值是1 => 当前计算数1 + 上一次计算的和total

如果输入值是x => 当前计算数x + 上一次计算的和total

计算 sum(5, 0)的时候，其过程是这样的:

sum(5, 0)
sum(4, 5)
sum(3, 9)
sum(2, 12)
sum(1, 14)
15

整个计算过程是线性的，调用一次 sum(x, total) 后，会进入下一个栈，相关的数据信息和跟随进入，不再放在堆栈上保存。当计算完最后的值之后，直接返回到最上层的 sum(5,0)。

这能有效的防止堆栈溢出。

而且最happy的是，在ECMAScript 6，我们将迎来尾递归优化，享受只有LISP
HASKELL这些古典函数式语言才拥有的能力。通过尾递归优化，javascript代码在解释成机器码的时候，将会向while看起，也就是说，同时拥有数学表达能力和while的效能。

使用尾递归

这里有一个使用尾递归提取绝对文件名的例子，可以来展示下尾递归的魅力。这个函数需要输入一个(或几个)目录名和当前所在的文件位置，然后会递归提取目录下的所有文件名，放入一个栈中。

var FS = require("fs");
var PATH = require("path");

function readSync(paths, i) {
    if (i >= 0 && i < paths.length) {
        var stats = FS.statSync(paths[i]);
        if (stats.isFile()) {
            return readSync(paths, ++i);
        } else if (stats.isDirectory()) {
            var newPaths = FS.readdirSync(paths[i]).map(function (path) {
                return PATH.join(paths[i],path);
            });
            return readSync(paths.slice(0, i).concat(newPaths, 
                                                     paths.slice(i + 1)), 
                            i);
        } else {
            return readSync(paths.slice(0, i).concat(paths.slice(i + 1)), 
                            i);
        }
    } else {
        return paths;
    }
}

测试一下，这个函数可以在服务器启动时，提取某一个(或者几个)目录内的所有文件，然后用于编译或者是其他的操作。

readSync([PATH.join(__dirname, "./tpls")], 0).forEach(function (path) {
    console.log(path);
});
readSync([PATH.join(__dirname, "./tpls"), PATH.join(__dirname, "./pages")], 0).forEach(function (path) {
    console.log(path);
});

文章来源：http://www.jianshu.com/p/269ba1ba1644

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/85386.html

《javascript语言精粹》学习笔记 - 递归函数

摘要：递归函数就是会直接或者间接地调用自身的一种函数。一般来说，一个递归函数调用自身去解决它的子问题。书上第二个例子是说递归函数可以非常高效率的操作树形结构，比如。有一些语言提供了尾递归的优化。好运的是，给我们带来了尾递归，详细迎接使用尾递归。递归函数就是会直接或者间接地调用自身的一种函数。递归是一种强大的编程技术，它把一问题分解为一组相似的子问题，每一个都用一个寻常解去解决。一般来...

Ryan_Li 2019-08-21 10:28 评论0 收藏0
Javascript 深入学习循环

摘要：递归函数还会受到浏览器调用栈的大小的限制。虽然迭代也会导致性能问题，但是使用优化的循环就可以代替长时间运行的递归函数，可以提高新能，因为运行一个循环比反复调用一个函数的开销要小。本文章记录本人在深入学习js循环中看书理解到的一些东西，加深记忆和并且整理记录下来，方便之后的复习。选择正确的循环体在大部分编程语言中，代码执行的时间多数消耗在循环的执行上。 js定义了4种...

Cristalven 2019-08-22 10:57 评论0 收藏0
ECMAScript6 新特性——“函数的扩展”

摘要：返回空字符串，返回将一个具名函数赋值给一个变量，则和的属性都返回这个具名函数原本的名字。不可以使用对象，该对象在函数体内不存在。等到运行结束，将结果返回到，的调用帧才会消失。 1 函数参数的默认值 ES6允许为函数的参数设置默认值，即直接写在参数定义的后面： function log(x = message.,y = duration infomation.) { consol...

Jiavan 2019-08-19 18:04 评论0 收藏0
JS的函数调用栈有多深？

摘要：中尾递归优化支持尾递归优化如果一个函数的最后一个操作是函数调用，那么将会用跳转而不是子调用。自从年双十一正式上线，累计处理了亿错误事件，付费客户有阳光保险核桃编程荔枝掌门对微脉青团社等众多知名企业。译者按：有时候会遇到Maximum call stack size exceeded的问题，本文教你stack size的计算方法。原文: The maximum call stac...

AprilJ 2019-08-22 18:20 评论0 收藏0
ES6学习第七章函数的扩展

摘要：前言本章介绍函数的扩展。形式为变量名，函数的最后一个命名参数以为前缀。规定只要函数参数使用了默认值解构赋值或者扩展运算符，那么函数内部就不能显式设定为严格模式，否则会报错。箭头函数不能用作构造函数。尾递归函数调用自身，称为递归。前言本章介绍函数的扩展。有些不常用的知识了解即可。本章原文链接：函数的扩展。函数参...

番茄西红柿 2021-11-29 10:50 评论0 收藏2637