JavaScript的递归以及浅谈尾调用

发表于 | 分类于 | 阅读次数:
字数统计: 1,967 | 阅读时长 ≈ 7

一个递归引发的血案

案发现场

今天看到了递归，测试的时候必须是经典的 Fibonacci （斐波纳契） 数列,然后我做的时候的代码如下：

1
2
3
4
function Fibonacci (n) {
  if ( n <= 1 ) {return 1};
  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

这是一个很简答的递归函数，单纯且不做作。他很简单，看一眼就知道他是如何运算的，单纯到到计算一个Fibonacci(100)就给我来个栈溢出错误(stack overflow)，然后我很奇葩的算了一下Fibonacci(25)，然后就卡-住-了，这不行啊，所以我就去搜原因去咯。

抢救现场

找了一下，找了一个有优化效果的函数：

尾递归优化后的程序源程序连接
1
2
3
4
var fibArr =[0,1,1];
function Fibonacci(n){
    return  fibArr[n]? fibArr[n]:(fibArr[n]=Fibonacci(n-1)+Fibonacci(n-2));
}

案件复盘

嗯，解释这个程序的思想之前我们先来看一下我们以前的程序都干了什么，在这之前我们先来补充一个小知识点：

我们知道，函数调用会在内存形成一个“调用记录”，又称“调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方，还会形成一个B的调用帧。等到B运行结束，将结果返回到A，B的调用帧才会消失。如果函数B内部还调用函数C，那就还有一个C的调用帧，以此类推。所有的调用帧，就形成一个“调用栈”（call stack）。


通过上面我们知道了，要是每次调用都会在内存生成一个调用帧，然后我们看一下Fibonacci数列，我们单步进入程序的时候（或者在纸上画一下）可以发现，我们一开始的程序在计算的时候会压入很多重复的计算，也就是说很多调用帧的返回结果是相同的，但是我们还是把他们压入到了调用栈里面，（函数先计算+左边的，然后就不断的进入函数内部，不断的压栈，计算完成后再一层一层的往回出栈，等到+左边的计算完了，再来右边的，你会发现右边的很多调用帧的结果刚才都算出来了，可是在算+左边结果的时候又把它们清除了，这样子是不是浪费了大把的时间）这样一来就是两个结果，栈不够用爆掉啦，栈将将够用，然后程序慢慢进再慢慢的出，这时候好的电脑运行会变慢，差的电脑就会卡住或者死机，让我哭一会。

引入尾调用

我哭好了，我们继续看优化后的函数，优化后的函数优化就是优化了重复的那个一部分，我们用数组来存储+左边我们每一个调用帧计算的结果，到计算+右边的时候我们直接和数组里面的数字（注意那个n）进行比对,准确的说是看参数是否相同，相同的话就直接出返回结果而不进栈了。
这里其实用到了一点缓存区的概念（这个我们有空再聊哈），我们这样子优化的直接效果就是进去的调用帧少了，直接结果是栈不会爆了，也没有了多余的重复计算，速度直接就上去了。
那么问题来了，是不是递归都会有这个问题，答案是：一些形式的递归是的，这个由JavaScript的栈机制造成的。
是不是要说，一些形式是的，那不就是还有形式不是，好了，我要开始装逼了，那个形式就是：尾调用。
直接上阮一峰大佬的解释：

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

1
2
3
function f(x){
  return g(x);
}

上面代码中，函数f的最后一步是调用函数g，这就叫尾调用。
以下三种情况，都不属于尾调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

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

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

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

1
2
3
4
function f(x){
  g(x);
  return undefined;
}

尾调用不一定出现在函数尾部，只要是最后一步操作即可。

1
2
3
4
5
6
function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

上面代码中，函数m和n都属于尾调用，因为它们都是函数f的最后一步操作。

关于尾调用的优化

好了现在知道了尾调用，按道理我应该引入尾调用的优化，毕竟ES6第一次明确规定，所有 ECMAScript 的实现，都必须部署“尾调用优化”。这就是说，ES6 中只要使用尾递归，就不会发生栈溢出，相对节省内存。
也就是说，尾调用是一写法形式，写成这样子，浏览器会自动进行优化（不过目前只有苹果的才支持，其它的浏览器需要在严格模式下才执行这个操作），又或者我们可以写一个函数，自己来做这个尾调用优化，但是我依稀还记得 Eloquent_JavaScript（第二版） 中有一句话：

The dilemma of speed versus elegance is an interesting one. You can see it as a kind of continuum between human-friendliness and machinefriendliness. Almost any program can be made faster by making it bigger and more convoluted. The programmer must decide on an appropriate balance.

Marijn HaverbekeEloquent_JavaScript

其实自己进行优化的方式也只是把递归转化成循环的样子，有的人会坚持尽可能的用循环而不是用递归，应为为达到同样的效果用循环更快，其实二者那个好都说不好的，或许等到浏览器都支持在正常模式下也进行尾递归优化的时候，递归就用的越来越多了，毕竟他有其独到的优势哈。

递归函数的规则

最后附上一个写递归函数的规则：

当编写递归例程的时候，关键是要牢记递归的四条基本法则:

  1. 基准情形。必须总有某些基准情形，它无须递归就能解出。
  2. 不断推进。对于那些需要递归求解的情形嗯每一次递归调用都必须要使求解状况朝接近基准情形的方向推进。
  3. 设计法则。假设所有的递归调用都能运行。
  4. 合成效益法则(ωmpound interest rule ) 。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。
Mark Allen Weiss·著 冯舜玺·译数据结构与算法分析：C语言描述（第2版）

以下是本博文参考的资料，感谢他们的分享

数据结构与算法分析：C语言描述（第2版）
阮一峰大佬的：ECMAScript 6入门
phpstudy的文章
jxgz_leo的博客。关于尾数调用优化，这个博文写的比阮大佬能详细

感觉不错的话给博主赞助一下呗