[翻译]函数式编程：Trampolines & Tails

原文地址：

https://medium.com/@cukejianya/functional-js-trampolines-tails-88723b4da320

翻译：

? ? ? ?函数式编程是现在的新热潮。虽然面向对象编程依然是主流，但少量新的 JS 框架和构思正在慢慢转为函数式编程的思想。在这篇文章中，我不会解释到底什么是函数式编程，但是假如你对今天所学觉得很感兴趣，那么我极力推荐你去探究更多关于函数式编程的内容。

Trampolines&Tails

? ? ? ? 我第一次听说?trampolines?是在?node school 的?functional-javascript?练习中。当时我没有了解这个题目的内容，并且没有意识到要了解这个问题的前提是要了解尾递归（tail recursion）。

functional-javascript相关练习14题

Recursion

? ? ? 在我们深入尾递归之前，我们首先需要讲讲递归。假如你是一个数学发烧友或者者参与过数学证实课程，那你应该以前就听过这个词。递归函数就是一个在自己内部使用少量修改过的参数又连续地调用了自身的函数，这种连续调用一直持续到最终它拿到一个基础返回数据。经典的递归函数例子——阶乘。

function factorial (n) {

? ? if (n === 1) {

? ? ? ? return 1;

? ? ?}

? ? return n * factorial (n — 1);

}

? ? ?实际上的执行过程：

factorial(4) = 4 * factorial(3) = 4 * (3 * factorial(2) ) = 4 * (3 *(2 *factorial(1)))= 4*(3(2 * (1))) = 24

? ? ? 递归可以使代码更加易读，但是它的使用受到少量限制。假如一个函数进行了太多的嵌套调用，即可能会发生堆栈溢出。每一次调用函数，这个函数的调用就会被推到已分配内存的调用栈中。而调用栈的大小有限制，只能容纳肯定数量的方法调用。因而才会发生上述的堆栈溢出问题。我们使用尾调用可以处理这个问题。

? ? ? 递归产生堆栈溢出：

factorial(4)? ? // 24

factorial(50000)? ?//RangeError: Maximum call stack size exceeded

Tail Recursion

? ? ? 尾递归是函数式编程中的一个重要特性。普通递归和尾递归之间的细微区别不单单是将函数当做操作数使用，而是将发生变化的结果传递到下一个递归的步骤中。这样即可以防止发生堆栈溢出。下面是一个尾递归例子：

function factorial(n) {

? ? var recur = function (result, n) {

? ? ? ? ? ?if (n === 1) return result;

? ? ? ? ? ?return recur(result * n, n — 1);

? ? }

? ? return recur(1, n);

}

? ? ? 实际上的执行过程：

factorial(4) = recur(1, 4) = recur(4 * 1, 3) = recur(4 * 3, 3) = recur(12 * 2, 2) = recur(24 * 1, 1) = 24

? ? ? ?这种操作非常棒，但是…?

? ? ? ?在 javascript 中，这个阶乘函数依旧会导致堆栈溢出(?_?)。由于尾递归是一项需要在语言级别实现的功能。在实现了尾递归的语言中，解释器/编译器将会把最后一个要被执行的函数视为递归函数，并且在返回函数最终的值时不需要进行其余任何的操作。而后解释器/编译器通过消除调用栈中之前多余的函数来优化尾调用。但是在 javascript 中，尾调用不能被解释器/编译器识别，因而依旧会被放置于调用栈。

Trampoline

? ? ? ?你可能会问，这跟?trampolines?有什么关系？没错，trampolines?是 javascript 中一个帮助实现尾递归的助力函数。假如你已经读过了其余的少量文章，你也许听过像?thunk?和trampolining?这样的词。thunk?通常只是一个尚未进行调用的函数。你可以大概理解到它通过像currying 和 binding 这样的特性（直译）。我们将一个 thunk，一个绑定函数作为参数传入trampoline 函数中，并在其中进行?while 循环，去调用它们的递归函数，直到传入的这个参数类型不再是函数类型。

function trampoline(fn) {

? ? ?while (fn && fn instanceof Function) {

? ? ? ? ? ?// 假如 fn 不是 underfined/null? 并且 fn 依旧是函数类型时继续循环

? ? ? ? ? ?fn = fn();

? ? ?}? ?// 我们调用这个函数，并且将调用之后的结果返回给新的 fn

? ? ?return fn;

? ? ? ? ?// 当 fn 是最终的结果，而不再函数时我们将 fn? 返回出去。

}

function factorial(n) {

? ? ?var recur = function(result, n) {

? ? ? ? ? ?if (n === 1) return result;

? ? ? ? ? ?return recur.bind(null, result * n, n – 1);

? ? ?}

? ? ?return trampoline(recur(1, n));

}

? ? ? ?我们来推演一下?factorial(4)?的执行过程。在上面的这个例子中，thunk 就是 recur 函数。当我们将?recur(1, n)?传给?trampoline?函数的时候，我们跳过了一步。由于当我们传递?recur(1, 4)的调用时，实际上我们传递了?recur.bind(null, 1 * 4, 3) 而不是?recur(1, 4)?本身。之后在 while 循环中检查了传入的?recur?能否为非 undefined/null?值，能否是一个函数。旁注：recur 是经过 bind? 绑定的，因而它仍是 Function 对象的一个实例。

console.log(recur.bind(null, 1 * 4, 3))? ? ?// [Function: bound recur]

? ? ? 由于 recur 可以通过 while 循环的两个条件，因而它将被执行，并且将其结果重新分配给 fn变量。现在 fn? 是?recur.bind(null, 4 *3, 2). 这个循环一直进行，直到?recur.bind(null, 12*2, 1)?被执行，最后返回值为24。24 为非 undefined/null, 因而它可以通过这个条件判断，但是24不是一个函数类型，这一个条件未通过，循环结束。所以最终 trampoline 函数返回的 fn 为24。

? ? ? 在这整个过程中，我们素来没有堆叠过函数调用。每一个函数被调用之后返回一个绑定过的函数，而后前一个函数就从调用栈被移除。我们使用 trampoline 函数的循环通过调用被绑定函数来跳过了每一个递归步骤。 酷~~~~??????

? ? ?在 ES6 中不需要?trampoline 这种解决，由于尾调用优化在 ES6中本身就是一个特性。但是要注意的是在任何的主流浏览器或者者 nodejs 中还没有相关的实现。