关于javascript:神奇的尾递归

置信递归大家都不生疏，在平时的开发中也常常用到。能够说递归它是一把双刃剑，要害看你怎么用它，用得好，它就是你手中的一把利剑，用得不好，小心伤到本人！最近看到了一种好的递归办法—尾递归，我集体感觉十分有用，而后再看一下本人以前写的对于递归的代码，的确很多都没有思考应用尾递归的办法。所以，在这里，想和大家讨论一下尾递归这个神奇的货色。

递归，简略来说，就是本人调用本人。

递归的益处就是使代码变得简洁；害处有二，其一就是对于刚接触编程的人来说并不敌对，不如迭代容易了解；其二就是如果使用不当的话很容易造成运行超时，重大的话会照成过程解体。

针对下面所说的两点害处，上面给出解决办法，第一个好解决，应用函数栈的概念就很好了解。上面采纳一段代码和一张图发表一下我集体对递归的了解。

阶乘的计算问题
置信大家都晓得阶乘，n 的阶乘就是 n! = n (n-1) (n-2) …. 1；那好，接下来的这段函数就是用来计算 n 的阶乘的。

function factorial(n) {if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

上面就用一张图联合 函数栈 来阐明一下这个函数是如何执行的。

下面的正方形大方框就是函数栈，factorial(5)、factorial(4)、factorial(3)、factorial(2)、factorial(1)顺次入栈，依照栈后进先出的法则，factorial(5)是最初才出栈的，这才算是执行完了 factorial(5)这个函数。乍一看，这没问题啊，不挺好的吗，一个接着一个出栈，然而如果不只是算 5 的阶乘，我想算 100 甚至 10000 的阶乘呢？这样函数栈就会有上万个函数期待出栈，这就很容易造成“栈溢出”谬误（stack overflow）。

再看上面一个例子，也是这种问题：

2. 斐波那契数列第 n 项的计算问题

置信斐波那契数列大家应该都不生疏，如果没听过的话，也没关系，这里简略介绍一下，其实它是一个这样的货色：

[1, 1, 2, 3, 5, 8, …]，到了这里大家有没有发现有什么法则？没发现？没关系，接着看：其实斐波那契数列是一个有着这样法则的数组，a[n] = a[n-1] + a[n-2] (n >= 2)，说白了，就是数组中任何一项都等于后面两项的和。

OK，到这里，置信大家都对斐波那契数列有了肯定的概念，那接下来的这段代码就是用来计算斐波那契数列的第 n 项。

function Fibonacci (n) {if ( n <= 1) {return 1};

  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89
Fibonacci(100) // 超时
Fibonacci(500) // 超时

这里就呈现问题了，计算第 10 项没有问题，然而当我应用这种递归形式去计算第 100 项甚至是第 500 项时，发现整个程序都解体了，起因很简略，就是下面所说的“栈溢出”谬误造成的。这有点相似于内存得不到清理造成内存透露，重大的话会造成整个应用程序解体。

读到这里，如果对递归不理解的小伙伴会问：为什么栈上面的函数要等到栈下面的函数出栈之后能力出栈呢？为什么会有这样一层依赖关系？没关系，带着这个疑难接着读上来。

尾调用（Tail Call）是函数式编程的一个重要概念，自身非常简单，一句话就能说分明，就是指 某个函数的最初一步是调用另一个函数。

function f(x){return g(x);
}

下面代码中，函数 f 的最初一步是调用函数 g，这就叫尾调用。

然而，留神，有一些状况会让人混同。上面列举的三种状况就不是尾调用。

// 状况一
function f(x){let y = g(x);
  return y;
}

// 状况二
function f(x){return g(x) + 1;
}

// 状况三
function f(x){g(x);
}

下面代码中，状况一是调用函数 g 之后，还有赋值操作，所以不属于尾调用；状况二也属于调用后还有操作，即便写在一行内。状况三等同于上面的代码。

另外，尾调用不是指调用呈现在函数的开端，而是指调用呈现在函数的最初一步。比方上面这段代码也是属于尾调用。

function f(x) {if (x > 0) {return m(x)            // 如果 x > 0, 这就是该函数执行的最初一步
  }
  return n(x);
}

好了，后面讲了这么多，重头戏来了，要解决在第二点中呈现的“栈溢出”谬误问题，尾递归是一个不错的办法。

函数调用本身，称为递归。如果尾调用本身，就称为尾递归。

递归十分消耗内存，因为须要同时保留成千上百个调用帧，很容易产生“栈溢出”谬误（stack overflow）。但对于尾递归来说，因为 只存在一个调用帧，所以永远不会产生“栈溢出”谬误。

看到尾递归的概念，我过后就有点纳闷，为什么一般的递归就要在函数栈外面保护多个调用帧，然而对于尾递归来说只存在一个调用帧？

其实只有略微比照一下尾递归和一般递归的代码就很容易搞懂这一点。

上面给出第二点中的两个例子的尾递归代码和一般递归代码的比拟。

1. 阶乘的计算问题

// 尾递归
function factorial(n, total) {if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

// 一般递归
function factorial(n) {if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

2. 斐波那契数列第 n 项的计算问题

// 尾递归
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {if( n <= 1) {return ac2};

  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity

// 一般递归
function Fibonacci (n) {if ( n <= 1) {return 1};

  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89
Fibonacci(100) // 超时
Fibonacci(500) // 超时

就拿第一个例子来探讨，先看一般递归的代码，真正递归的其实是这一句代码：return n factorial(n – 1); 再看一下尾递归的递归代码：return factorial(n – 1, n total); 其实尾递归这句代码可能写成这样更好了解：

// 一般递归本来的代码
return n * factorial(n - 1);

// 尾递归本来的代码
return factorial(n - 1, n * total);

// 能够写成这样
let n1 = n - 1;
let total1 = n * total;
return factorial(n1, total1);

一般递归和尾递归递归代码最大的区别就是：

一般递归：

当执行 factorial(n – 1)这句代码的时候，还援用着 factorial(n)函数作用域定义的 n，也就是：n * factorial(n – 1)，因为 n 被援用，所以导致 factorial(n)不能出栈。

尾递归：

然而尾递归不同就不同在这一点，尾递归执行递归的代码的时候没有持续援用 factorial(n, total)的变量，所以 factorial(n, total)能够顺利出栈。所以以此类推，尾递归在整个函数执行的过程中，函数栈至始至终都只有一个调用帧，所以也就不会产生“栈溢出”的问题。

由此可见，“尾调用优化”对递归操作意义重大，所以一些函数式编程语言将其写入了语言规格。ES6 亦是如此，第一次明确规定，所有 ECMAScript 的实现，都必须部署“尾调用优化”。这就是说，ES6 中只有应用尾递归，就不会产生栈溢出（或者层层递归造成的超时），绝对节俭内存。

所以，大家领会到尾递归的神奇之处了吗？

参考链接：阮一峰：尾调用优化

关于javascript:神奇的尾递归

一、引言

二、从递归说起

三、什么是尾调用

四、什么是尾递归

五、总结