共计 5119 个字符，预计需要花费 13 分钟才能阅读完成。
目录：
1. 简略递归定义
2. 递归与循环的区别与分割
3. 递归的经典利用
1. 简略递归定义
什么叫递归？（先定义一个比较简单的说法，为了了解，不肯定对）
递归：有限调用本身这个函数，每次调用总会改变一个要害变量，直到这个要害变量达到边界的时候，不再调用。
比如说我要你先求一个 N! 的后果
你说我会用循环啊（没错，然而当初是学递归）
int factorial(int x,int ans)
{if(x==1)
return ans;
factorial(x-1,ans*x);
}怎么样，对于 C 根底如果把握的还行的话，这段代码应该很好了解。递归，顾名思义就是“递”和“归”。也就是说，写每一个递归函数的时候，都应该在写之前思考分明，哪里体现了“递”，哪里体现了“归”。
然而经常递归函数会比较复杂，“递”和“归”看起来并不是那么显著，这就须要咱们进一步来了解递归算法的思维。
比如说我当初要你用辗转相除法求出两个数的最大公约数，递归函数如下：
int gcd(int a,int b)
{return a%b==0?b:gcd(b,a%b);
}这是一段很罕用的代码，咱们晓得，在学习过程中不求甚解是最不应该的。因而当初来认真看一看。这里的“递”和“归”放在同一行。首先进行判断a==b?（咱们能够设想成“归”的内容，如果这个条件合乎的话）。当然，如果不合乎这个判断，那就持续“递”，也就是持续进行gcd(b,a%b);
看到这里，你就会发现，递归不就是循环的另一种形式么？
说对了一半，不过递归是一种思维，当初还临时不能说透，须要大家先比拟一下循环和递归的相同点和不同点（饭一口一口吃，别着急）
2. 递归与循环的区别于分割
相同点：
（1）都是通过 管制一个变量的边界 （ 或者多个），来扭转多个变量为了失去所须要的值，而重复而执行的；
（2）都是依照事后设计好的推断实现某一个值求取；（请留神，在这里循环要更重视过程，而递归偏后果一点）
不同点：
（1）递归通常是逆向思维居多，“递”和“归”不肯定容易发现（比拟难以了解）；而循环从开始条件到完结条件，包含两头循环变量，都须要表达出来（比拟简洁明了）。
简略的来说就是：用循环能实现的，递归个别能够实现，然而能用递归实现的，循环不肯定能。因为有些题目①只重视循环的完结条件和循环过程，而往往这个完结条件不易表白（也就是说用循环并不好写）；②只重视循环的次数而不重视循环的开始条件和完结条件（这个循环更加无从下手了）。
3. 递归的经典利用
来看看“汉诺塔问题”
如图，汉诺塔问题是指有三根杆子 A,B,C。C 杆上有若干碟子，把所有碟子从 A 杆上移到 C 杆上，每次只能挪动一个碟子，大的碟子不能叠在小的碟子下面。求起码要挪动多少次？
这是一个循环只重视循环次数的常见例子，咱们晓得，用循环有点无从下手（就目前作者程度来看），然而递归就很好写了。
汉诺塔，什么鬼，我不会啊？
别急，慢慢来。
咱们首先须要一点思维：解决 n 块盘子从 A 挪动到 C，那么我只须要先把 n - 1 块盘子从 A 移到 B，而后把最上面的第 n 块盘子从 A 移到 C，最初把 n - 1 块盘子从 B 移到 C（这就实现了）。
等等，那么如何把 n - 1 块盘子从 A 移到 B？
很好，这阐明你曾经开始递归入门了。
同样这样去想：解决 n - 1 块盘子从 A 挪动到 B，那么我只须要先把 n - 2 块盘子从 A 挪动到 C，而后把倒数第二块盘子从 A 移到 B，最初把 n - 2 块盘子从 C 移到 B（这就实现了）。
这就是递归的“递”！
那么“归”呢？n== 1 的时候？
Bingo
int i; // 记录步数
// i 示意进行到的步数, 将编号为 n 的盘子由 from 柱挪动到 to 柱(指标柱)
void move(int n,char from,char to){printf("第 %d 步: 将 %d 号盘子 %c---->%c\n",i++,n,from,to);
}
// 汉诺塔递归函数
// n 示意要将多少个 "圆盘" 从起始柱子挪动至指标柱子
//start_pos 示意起始柱子,tran_pos 示意过渡柱子,end_pos 示意指标柱子
void Hanio(int n,char start_pos,char tran_pos,char end_pos)
{if(n==1) // 很显著, 当 n == 1 的时候, 咱们只须要间接将圆盘从起始柱子移至指标柱子即可.
move(n,start_pos,end_pos);
else
{Hanio(n-1,start_pos,end_pos,tran_pos); // 递归解决, 一开始的时候, 先将 n - 1 个盘子移至过渡柱上
move(n,start_pos,end_pos); // 而后再将底下的大盘子间接移至指标柱子即可
Hanio(n-1,tran_pos,start_pos,end_pos); // 而后反复以上步骤, 递归解决放在过渡柱上的 n - 1 个盘子
// 此时借助原来的起始柱作为过渡柱(因为起始柱曾经空了)
}
} 实际上这外面曾经应用到了一点点栈的思维（即最下面的最先思考变动），但其实递归有的时候就是真的能够了解为栈！
到了这一步，置信大家应该曾经有所明确。循环其实就是一个控制变量从开始条件走到完结条件的过程（在循环的过程顺带把其余变量也扭转一下），因而须要控制变量，开始条件，完结条件（缺一不可）。然而递归只有通知你“归”是什么，如何去“递”，不论过程如何，只有计算结果即可。
（2）递归能够是多个“递”，也能够是多个“归”；而循环由始至终都只由一个变量管制（就算有几个变量同时管制）也只有一个进口，每次循环也只是一个“递”。
再看一个例子
用二分思维建设二叉树（通常的是递归实现），比如说 线段树
//root 节点序号
//left 节点保护的左边界
//right 节点保护的右边界
void build(int root,int left,int right)
{if(left==right)
return ;
int mid=(left+right)/2;
build(root*2，left,mid);
build(root*2+1,mid+1,right);
}如果你是老手看不太懂也没关系，当初最次要的是明确：在这个程序外面只有一个“归”，然而有两个“递”。
那么如果学过一点然而对这一块还不明确的怎么办呢？别急，听我来解释：
实际上，这两个“递”是依照先后别离进行的，等到第一个“递”执行完（也就是到了“归”的条件之后），才开始执行第二个“递”。也就是说，通常在建树的时候，都不是一层一层同时建的，而是先建一棵子树，等到这棵子树全副建完之后，才开始建设另外一棵子树。
那就会问了，一棵子树建完了之后 root 值不会变么，root 值变了之后还怎么建另外一棵子树呢？
root 值不会变！大家请留神，这里 root* 2 是写在递归函数外面的，实际上并没有赋值？为什么要这样写？因为如果不这样写，你间接写在外边的话，一棵子节点达到叶子节点之后，须要一层一层往上回溯（在这里提到了 回溯 的思维），而回溯就会无端产生很多不必要的工夫复杂度，升高了递归效率（实际上递归的工夫效率原本就有一点偏低）。
所以到目前为止，我只是介绍一些很常见的简略的递归，然而在接下来，我就须要说一些比拟深层一点的常识了。
首先要了解一下什么是回溯（写的不好，大佬勿喷）
回溯：在递归的过程中因为扭转的量须要倒退到某一个地位而执行的步骤。
先来看一个简略的 素数环 问题：
给出 1 到 n 的 n 个间断的正整数（这里 n 临时等于 6），并且把这 n 个数填写在如下图的 n 个圆圈外面（当然是不反复不脱漏了）。要求是每一个地位下面的数跟他相邻的数之和都为一个素数，打印并输入最初满足条件的状况。
首先明确，开始条件是 1，把 1 填写在第一个地位，而后在剩下的 n - 1 个数字里找到一个满足与 1 的和是一个素数的数（当然如果有多个，先靠前的先思考）。接下来再持续从剩下 n - 2 个数字里找到一个与这个数的和又是一个素数的数（当然如果有多个，同上。）。。。最初的一个数只有满足与最开始的数 1 之和是一个素数的话，这个状况就满足了（就能够打印输出这样一个例子了）
但事件并没有设想的那么简略。。。（通知我如果在中途寻找的过程中从剩下的数里找不到与以后数的的和是一个素数的状况呈现怎么办？在线等）
这就表明这样一条路终归是一条思路，你要往回走了！这就很合乎咱们给回溯的定义了，此时这个扭转的量须要倒退的后面一步从另外一个方向寻找了。（还是举栗子吧）
比如说：
1->2->3->4 忽然发现 5 和 6 都不满足要求了
那么就倒退，筹备找另外满足要求的数
1->2->3 又发现除了 4 以外 3 跟 5 或者 3 跟 6 也不满足要求
那就持续倒退，持续筹备找另外满足要求的数
1->2->5->6 接下来发现 6 跟 3 或者 6 跟 4 不满足要求
…(还想继续下去？你是要玩死我？别这样，我也累啊，看一两个就行了，啊！)
最初发现满足条件的一个是
1->4->3->2->5->6
大家应该曾经懂了，下面的倒退，实际上就是回溯。（临时这样简略的了解吧，错了也不能怪你们）
实际上，递归 + 回溯就曾经是 dfs(深度优先搜寻)的内容领域了。
void dfs(int x)
{if(x==n+1&&prime(a[x-1]+a[1])) // 如果满足条件就能够打印输出数据了，这里就是“归”{for(int i=1;i<n;i++)
cout<<a[i]<<" ";
cout<<a[n]<<endl;
}
else // 否则就持续“递”{for(int i=2;i<=n;i++)
{if(!vis[i]&&prime(i+a[x-1]))
{vis[i]=1; //vis[]是一个标记数组，示意以后的数字曾经被应用过了
a[x]=i;
dfs(x+1); //“递”的入口
vis[i]=0; // 请留神，回溯点在这里
}
}
}
}大家可能后面都看懂了，比如说“递”和“归”，vis[]标记数组什么的。然而最初一个 vis[i]= 0 是啥意思？难道不多余么？
不多余！后面我曾经拿建树给大家讲过递归的“工作原理”，它是先有限递归，而后达到某个条件之后，回溯到下面一个地位，持续向其余方向递归。而这个 vis[i]= 0 就是分明以后数字的标记，示意从以后节点开始，之后递归过的内容通通清空（也就是回溯）。而后依据循环，进行上面一个方向的持续递归。
这也是 dfs 的经典思维所在！
因而，讲到这里，不说说 dfs 仿佛也是吊大家胃口了。所以接下来，就聊一聊 dfs 中的递归。
比如说 hdu 下面的 1312 http://acm.hdu.edu.cn/showproblem.php?pid=1312
我简略说一下意思，如下图，判断一个图内包含 @符号在内的所有‘.’和‘@’的个数。有个限度条件，如果‘.’被‘#’封死，则‘.’不可拜访。
6 9（别离示意行和列）
....#.
.....#
......
......
......
......
......
#@...#
.#..#.45
比如说这一个数据就有三个‘.’被边界和‘#’困死而不可拜访，因而只有 45 个点满足要求。
本题的思路就是从’@’ 点开始，bfs 搜寻每一个点，分成上下左右四个方向别离递归搜寻。
int cnt,a[4]={-1,0,1,0},b[4]={0,1,0,-1},n,m,vis[22][22];
char s[22][22];
void dfs(int x,int y)
{for(int i=0;i<4;i++) // 四个方向循环搜寻
{int p=x+a[i];
int q=y+b[i];
if(p>=0&&p<m&&q>=0&&q<n&&!vis[p][q]&&s[p][q]=='.') // 判断递归条件，包含在数组边界之内，该点未被标记
{vis[p][q]=1; // 标记该点
cnt++; // 计数变量加一
dfs(p,q); // 递归搜寻
}
}
}请留神：本题中因为能够提前判断下一个要搜寻的点是否为‘#’而免于回溯，升高工夫复杂度。
并且大家能够看出，下面的代码实际上是略微简单一点的递归算法（把从‘@’登程的每一个方向看成一条线段，而这条线段的另外一个起点就是边界或者’#’），因而这就是能够看成循环了四次的递归算法，而每一次递归调用的过程，每一方向又看成从以后点登程的一条线段。如此重复。（两头的 cnt 用来计数）
请留神，cnt 就是就是递归的次数（因为没有回溯，如果有回溯，计数的话不肯定等于递归的次数）
到此，根本知识点曾经全副讲完，上面给出一点集体对于写递归算法的倡议吧：
（1）把递归当成简单的循环来写，如果不明确过程，多模仿几遍数据；
（2）把递归逆向写的时候当做一个栈来实现（即合乎后进先出的思维）；
（3）当递归和回溯联合在一起的时候须要明确递归次数和统计次数之间的练习和区别；
（4）但递归有多个“递”和“归”的时候，抉择一个重点的“递”和“归”作为匹配，即时题目即时剖析，留神随机应变即可。
