技术必备，递归

技术必备，递归

对于开发来说 ，常用的辅助技能，辅助知识不管是为了自己开发时候的便利性，还是工作中的需要，都是不可或缺的一部分，于是这里就简单的说下递归

文章要点

• 递归是什么
• 递归怎么用
• 使用递归需要注意什么

递归是什么？

说到递归，咱们先来了解下迭代，递归可以说是迭代的特例，二者有相似之处也有区别

递归，简单的说就是自己调用自己，自己包含自己
迭代，简单的说就是将输出作为输入,更新内部的值

上面的代码是直接在浏览器的控制台编辑js代码的，我们可以看到整个循环就是改变num 的值，num = num + i这个语句我们可以看到，右边的num就是以输入值的形式进行运算的，但是他的值又是来源于上一个循环的输出值，所以就有了

num = 0;  //初始化
num = 0+0;  //第一个循环，此时num的输出值为0
num = 0+1;  //第二个循环，此时num为0作为输入值，计算得到新的num值为1
num = 1+2;  //第三个循环，此时num为1作为输入值，计算得到新的num值为2
3 = 3；  //不满足循环条件，退出，输出结果值 3

这是一个很典型的斐波那契数列，1、1、2、3、5、8、13…..就是前两个数的和等于这个数的数值，第一第二个数为1，于是我们就可以这样分析：

f5 = f4 + f3;
f4 = f3 + f2;
f3 = f2 + f1;
f2 = 1;
f1 = 1;
// 于是就可以用解方程的思想算出 f5 = 1+1+1+1+1 = 5;
// 我们可以发现对于`fn`我们也可以直接考虑`fn`前两个数的和就好了，
// 所以只要我们写出一个可以计算前两个值的和的函数，
// 然后再通过不断的调用这个函数，传入不同的参数，我们就可以得到我们的结果

整个运行的过程大致是这样:
fun(5)
fun(4) + fun(3)
((fun(3) + fun(2))+(fun(2) + fun(1))
(((fun(2) + fun(1)) + fun(2))+(fun(2) + fun(1))
(((1+1)+1)+1+1)
5

递归虽然简化了我们的计算量，但是细节问题，不注意就会适得其反，所以使用递归的时候我们需要注意三大问题：尤其有注意递归的结束条件

1.（递归前进段） 提取重复的逻辑部分（上例中的是，每个数等于其前两个数的和）
2. （递归边界段）控制逻辑边界，什么时候停止调用自身（上例中的是，当num = 1或者num = 2的时候）
3. （递归返回段）结束的时候停止执行（退出）

递归怎么用？

递归在生活中并不罕见，递归的出现，给我们带来了极大的便利，但是也有其弊端，递归相对于常用的循环结构，在某种情况下效率并没有优势，反而会显得比较复杂，所以选择递归的时候要适当，那我们要在什么时候选择递归会比较好呢？

其主要用于解决三类问题

• 回溯算法——用递归解决问题
• Fibonacci，阶乘——用递归定义问题数据
• 二叉树的遍历，图的遍历——用递归定义问题的结构

回溯算法类似枚举搜索的过程，是一种深度优先搜索的策略，简单的说就是，先在一条路试着走走，走不通了之后就回来再重新走别的路

二叉树的遍历有三种：前序遍历、中序遍历、后序遍历
访问结点本身(N); 遍历该结点的左子树(L); 遍历该结点的右子树(R)

• NLR 访问根节点的操作在遍历其左右子树之前
• LNR 访问根节点的操作在遍历其左右子树之中
• LRN 访问根节点的操作在遍历其左右子树之后

图的遍历：指的是从图中的任意一点出发，对每个点进行有且仅有一次的访问，涉及的算法主要有两个：

• 深度优先搜索法：就是上面所说的，先在一条路试着走走，走不通了之后就回来再重新走别的路
• 广度优先搜索法：就是按层次来访问，第一层访问完毕之后开始第二层…以此类推

使用递归需要注意什么？

• 使用递归需要注意最重要的一点就是要有结束条件。
• 递归可以解决复杂问题、缩短程序代码、提高编程效率等优点

函数在调用另一个函数时，需要把原来的函数的局部变量、返回地址等压入堆栈（即所谓的保留现场），以达到正常返回和继续执行。在一个函数进行递归调用时，每一次调用它本身，就象调用一个新的函数一样，他的所有的局部变量都要在内存中保留一份（即压栈），如果递归调用的层次过多，将出现“堆栈溢出错误”。因此选择递归需要看情况。

使用的时候需要注意：

为防止递归持续不断被调用，要有结束条件

递归但一般不能提高程序的执行效率。直接递归函数要不断的调用自身，而间接递归会调用两个以上的函数，占用内存空间，为避免这种情况，应尽量少用局部变量