“递归”是所有语言都有的一种常用操作，但是你真的用好递归了吗？对递归没有任何疑问了吗？觉得递归总是找不到感觉不知道该怎么写吗？这篇文章正是为此而生的

递归的本质就是函数调用而已，深入理解背后的原理你能轻松用好它

本文将包含以下内容

• 什么是递归
• 如何选择停止条件
• 递归的本质、递归是如何工作的
• 面试题、递归应用实例

快速介绍

递归是所有语言都很常见的特性，也是我们解决很多问题的利器，那么，什么是递归？

//最简单的理解，递归就是一个函数调用它自己
function blueFn(){
  blueFn();
}

blueFn();

当然，程序不能真的像上面那样写，不然函数会无止境的调用下去，最后只能报错

顺便一说，这个错误是“栈溢出”引起的，后面咱们会详细说这个问题，先继续往下看

递归的终止

程序中任何操作都不能无穷无尽的执行下去，递归也不例外，所以递归一定要有一个适当的**“终止条件”**——也就是说，到此为止不会再产生新的调用，看个例子——假设我们想求一个n的阶乘，也就是5!=5*4*3*2*1这种小学都做过的东西

function N(num){
  //5! = 5 * 4!
  return num*N(num-1);
}

N(5);

但这个程序不会正确终止，只会报错，和上面一样

为什么？因为这个函数永远会继续往下调用，但我们知道1!其实就“到头了”，因为1!=1，所以我们完全可以用1作为终止条件

function N(num){
  if(num<=1)return 1;
  else return num*N(num-1);
}

N(5);

所以我们看到递归最重要的两个特征：

• 函数调用其自身（直接的或间接的都算）
• 有明确的终止条件

算是见了个面，接下来我们从最基础的开始，彻彻底底的理解一下递归到底是什么

什么是递归思想？

万物皆可分

首先，绝大多数问题都可以划分成更小的问题，通过求解这些小问题，将结果合并在一起得到原本问题的答案，举几个例子：

• 库存清点：大型仓库如果一个人清点可能要好几个月才能完成
  • 解决方案：找20个人各自负责一块，然后把清点结果汇总
• 数组求和：假设有有20G的数据需要求和，需要运行很久才能出结果
  • 解决方案：找100台机器一起跑，每个负责200M，然后把各自的结果相加
• 搜索引擎：搜索引擎存储了数万亿页面，依靠单台服务器去找需要很久，但根据我们的经验，搜索结果0.x秒就能出来
  • 解决方案：每台服务器负责一部分数据，然后将各部分搜索结果合并为最终的搜索结果

从上面几个简单的例子里可以看出，解决大问题时，划分为更小的问题分别解决，然后将结果合并起来是一种有用的思路

细心的同学可能会说“诶，老师，这不就是google的MapReduce吗？” 是的，MapReduce就是分治法的应用，不过这是另一个话题，这里就不展开了

实例理解递归

递归就是对上面思想的应用——把大问题分解为更小的问题，从而便于求解

来看个问题吧，更容易理解

注意：此实例为了突出原理，简化了部分必要操作

假设，我们需要一个函数帮我们找到数组中的最大值

function findMax(arr){
  
}

解决这个问题当然有很多思路，循环、排序啥的都可以，不过这里，我们选择一个有意思的方法：

• 首先，我们把数组分成左、右两半
• 找出左侧的最大值maxL，再找出右侧的最大值maxR
• 比较maxL和maxR，找到最终结果max

//注意：严格来说这个函数会有问题，需要判断arr.length才完整——暂略
function findMax(arr){
  //终止条件：数组如果就1个值，它自己就是结果
  if(arr.length==1)return arr[0];
  
  //把数组分成左、右两半
  const center=ceil(arr.length/2);  //取个整，因为下标不能是"2.5"这种
  let arrL=arr.slice(0, center);
  let arrR=arr.slice(center, arr.length);
  
  //找出左侧的最大值`maxL`
  let maxL=findMax(arrL);
  //再找出右侧的最大值`maxR`
  let maxR=findMax(arrR);
  
  //比较`maxL`和`maxR`，找到最终结果max
  if(maxL>maxR)
    return maxL;
  else
    return maxR;
}

上面的例子中，我们并没有正面解决问题，反而采取了“逃避”的办法——递归本质上就是问题的划分和结果的合并

1. 把问题划分为更小的问题

   let arrL=arr.slice(0, arr.length/2);
   let arrR=arr.slice(arr.length/2, arr.length);
   

2. 分别求解

   let maxL=findMax(arrL);
   let maxR=findMax(arrR);
   

3. 把结果合并起来

   if(maxL>maxR)
     return maxL;
   else
     return maxR;
   

递归是怎么执行的

首先，假设我们有一组数据[12, 8, 96, 27, 3, 9, 81]

第一部分、分割

• 第1次，我们会把它分成两部分：[12, 8, 96, 27]和[3, 9, 81]
• 并且，带来两个新的函数调用findMax([12, 8, 96, 27])和findMax([3, 9, 81])
• 然后，每个数组都会被进一步划分为两部分，直到不可再分为止

第二部分、合并

• 每次，findMax都会将两边的结果（例如：12和8）进行比较，并将其中较大的作为结果
• 重复这个过程，直到所有函数返回，既能得到最终结果

递归的本质、停止条件

开始时我们就说过，递归需要明确的终止条件，否则会出现无限调用引发栈溢出的问题，那么我们有两个问题：

• 为什么会栈溢出？什么是栈溢出？它咋就溢出了
• 我们应该如何选择终止条件？

递归的本质

递归其实并不特殊，它依然是函数调用，只不过是自己调用自己（更专业的说法，函数是“可重入的”），所以理解递归最好的办法是先理解函数是如何工作的

函数调用栈

js和所有语言一样，内存中有一块专门存放函数调用的空间，称为“函数调用栈”，当我们调用函数或声明局部变量时，都是在操作它

直接看个程序吧，我们来看看它是怎么执行的

function blueFn(num){
  return sum(12, 5)+num;
}

function sum(a, b){
  return a+b;
}

let res=blueFn(99);
console.log(res+8);

第一步、它会从第9行开始执行，这时栈是空的

第二步，开始调用blueFn，这时会在栈上存储参数、返回位置等信息，并转到函数内部执行

第三步，碰上了新的函数调用sum(12, 5)，又进去一层

第三步，完成a+b的运算，并按照栈的要求返回，然后清理栈的信息

第四步，完成17+num的运算并返回，当然，也会清理栈的信息

最后，完成console.log(116+8)，整个程序结束

在这个过程中，我们能看到3点：

• 函数的调用通过栈完成
• 函数的参数、局部变量、pc指针等，通过栈传递
• 函数调用层级越深，栈存储的东西越多

栈的上限

计算机的资源是有上限的，js引擎为了保护自身的运行，不会允许你无限的往栈上放东西，所以函数栈有一个上限（不同语言不一样，但都不是很大），当然，这样做其实并不会对你有太多影响，因为程序正常时，栈的空间绝对够用

这种保护机制也能顺便帮我们找到错误的递归，总体而言是个有益的设定，那么下一个问题就是，我们如何选择合适的停止条件，确保我们的程序能正确的执行呢？

面试题、实例

题目1-数组的反转

有这样一个题目，要求大致是不用循环、不用reverse、不用这不用那反正就是各种疯狂暗示，让你用递归来解决，咱们就来试一下

let arr=[1,2,3];

function reverse(a){
  //在这里具体写东西
}

reverse(arr);  //希望得到反转后的[3,2,1]

先不着急写哈，我们来分析一下，既然要用递归，那么想清楚怎么用

[1,2,3] -> [3,2,1]

//我们可以看做
1 和 [2,3] -> [3,2] 和 1

//也就是说
arr[0] + arr[1...n] -> reverse(arr[1...n]) + arr[0]

有了这个思路，其实是非常容易完成的

let arr=[1,2,3];

function reverse(a){
  if(a.length<=1)return a;
  
  const [first, ...rest]=a;
  return [...reverse(rest), first];
}

reverse(arr);

题目2-不用循环遍历数组

跟上面那个类似的，就是不让你用for、forEach、while之类的，反正就是疯狂暗示用递归来完成一个循环，其实比第一个还简单不少

做法也比较简单，每次我们把数组分成第一个和其他，然后自己处理第一个，剩下的递归就完事了

function iterate(arr, callback){
  //结束条件
  if(arr.length==0)return;
  
  //把数组分成第一个和其他
  const [first, ...others]=arr;
  
  //自己处理第一个
  callback(first);
  //剩下的递归
  iterate(others);
}

总结

是时候梳理一遍Blue讲过的东西了，那么首先

• 狭义上，递归是指函数（直接或间接）调用它自身
• 广义上，递归是一种思想，我们可以把问题拆分为小块，分别求解，最后汇总得到整个问题的解
• 递归以及函数调用，本质上是在函数调用栈（call stack）中保存调用信息、参数，而调用栈有大小限制，超出会报错
• 递归的核心问题
  • 如何拆分问题、分别求解、合并结果
  • 如何选择合适的终止条件（重点）

有bug？想补充？

感谢大家观看这篇教程，有任何问题或想和Blue交流，请直接留言，发现文章有任何不妥之处，也请指出，提前感谢