理解递归及其应用

什么是递归算法？什么是递归函数？如何理解递归算法？如何理解递归函数及其应用？

递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。在程序语言中，程序调用自身的编程技巧称为递归。递归函数是指在运行的过程中函数直接或间接调用函数自身。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

理解递归

递归函数是指函数直接或间接调用函数本身。

这句话理解起来并不难，从概念上出发，理解递归函数：

function foo(){
  console.log("函数 foo 是递归函数。");
  foo();
}

这里的 foo 函数就是一个递归函数。

当你把这个函数拿到浏览器上运行的时候，你会发现内存溢出了，为什么呢？因为这个递归函数没有停止处理或运算的出口，因此这个递归函数就演变为一个死循环，即函数永无休止的调用自身。

因此，使用递归函数必须要符合两个条件：

递归表达式(规律)
递归出口(终止递归的条件)

递归其实和循环是非常像的，循环都可以改写成递归，递归未必能改写成循环，这是一个充分不必要的条件。

例如：求1+2+3+…+n的和。

分析：

当n=1时，和就是1
当n>1时，和就是1+2+3+…+(n-1)的和加上n。

于是得到了上面求和的数学定义：
$$
f(n) =
\begin{cases}
1, & \text{$n$ = 1} \\
f(n-1)+n, & \text{$n$ > 1}
\end{cases}
$$

使用for循环来实现求和1+2+3+….+n，那是很简单的：

var sum = function (n) {
  var result = 0;
  for (var i = 1; i <= n; i++) {
    result = result + i;
  }
  return result
}

前面说过，循环都可以使用递归来进行改写，递归实现如下：

var sum = function (n) {
  if (n == 1) {
    return 1;
  } else {
    return sum(n - 1) + n;
  }
}

递归的应用

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

数组中的最大值

使用用递归求数组中的最大值，那怎么用呢？首先还是先要找到递归表达式(规律)和递归出口。

1、找递归表达式(规律)：

将数组第一个元素->2与数组后面的数->[3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2]进行切割，将数组后面的数看成是一个整体X=[3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2]，那么我们就可以看成是第一个数2和一个整体X进行比较。
找出整体X的最大值又是和我们的初始目的(找出最大值)是一样的

2、找递归出口：

如果数组只有1个元素时，那么这个数组最大值就是数组的第一个元素。

技巧：在递归中常常是将问题切割成两个部分(1和整体的思想)，这能够让我们快速找到递归表达式(规律)

那么递归的实现如下：

var findMax = function (arr) {
  if (arr.length === 1) {
    return arr[0];
  }
  var a = arr[0];
  var b = findMax(arr.slice(1));
  
  return Math.max(a, b)
}

斐波那契数列

斐波那契数列（1，1，2，3，5，8，13，21，34，55，…..，n）是递归的典型应用案例。斐波那契数列的规律是：前两项之和等于第三项。

如：

1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
...

那么第n项是多少？第n项时第n-1和第n-2项的和，那么我们就可以很简单写出对应的递归表达式了：Z = (n-2) + (n-1)。递归出口有两个，因为它是前两项加起来才得出第三项的值。

用递归实现求斐波那契数列第n项的值，如下：

var fibonacci = function (n) {
  if (n === 1) {
    return 1;
  } else if (n === 2) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

递归优化——尾递归

递归和循环相比运行效率较低，即递归的性能不如循环。一般的递归容易造成栈溢出，即内存泄漏（内存不足）。

为什么递归运行效率较低？容易造成栈溢出？看下递归实现1+2+3+…+n求和的例子：

var sum = function (n) {
  if (n == 1) {
    return 1;
  } else {
    return n + sum(n - 1);
  }
}

当n=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

可以看出：当n=5时，因为要先求得sum(4)的结果，于是sum(4)就被压栈，内存无法释放；当求sum(4)时，同样的，要先求的sum(3)的结果，于是sum(3)也被压栈。以此类推，一直到递归的出口n=1时，被压住的栈帧才被逐步释放。

当n足够大时，就会造成栈溢出。经测试当运行sum(100000)时，Chrome浏览器的内存就被爆了，抛出错误：

1	Uncaught RangeError: Maximum call stack size exceeded

因此，需要对递归进行优化，其中尾递归是常用的一种方法。如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

要理解尾递归一定是尾调用，所以要理解尾递归就要先理解尾调用。

尾调用就是指某个函数的最后一步是调用另一个函数。尾调用是函数式编程的一个重要概念。

一个尾调用的例子：

1
2
3

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

以下两种情况，都不属于尾调用：

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

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

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

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

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

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

注意：尾递归一定是尾调用，反之不成立。

现在，用尾递归改写sum函数：

var sum = function (n, total = 1) {
  if (n == 1) {
    return total;
  } else {
    return sum(n - 1, total + n);
  }
}

当n=5时：

sum(5)

递归过程如下:

sum(5, 1)

sum(4, 5)

sum(3, 9)

sum(2, 12)

sum(1, 14)

15

上面尾递归的运行原理是：把递归顺序中倒数第一步的结果先求出来，当作参数传进递归函数中，最后返回求递归顺序中倒数第二步的结果，以此类推，直到递归出口。又因为，每次递归都只返回一个函数。因此，每次递归，递归函数的运算只依赖于自身的参数，即每次递归完成后内存都可以得到释放，不存在压栈的问题。

于是，尾递归可以定义为：最后一步只调用自身的递归函数。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。

尾调用优化对递归操作意义重大，所以一些函数式编程语言将其写入了语言规格。ES6也是如此，第一次明确规定，所有 ECMAScript 的实现，都必须部署”尾调用优化”。这就是说，在 ES6 中，只要使用尾递归，就不会发生栈溢出，相对节省内存。

注意：ES6的尾调用优化只在严格模式下开启，正常模式是无效的。

目前，大多数浏览器都没有尾递归优化功能，即使是node.js这项功能默认都是关闭的状态。因此，在开发过程中，除非是无法避免的情况，否则，尽量使用循环替代递归。