递归法：
通过自身调用自身来达到问题解决的算法。一般，我们用归纳法是证明递归算法正确性和进行算法分析
原问题无法解决，用分治的的思想将其分解，若分解后的子问题仍无法解决就再次分解，直到分成的子问题规模足够小可以直接解决，然后将子问题合并得到原问题的解。
递归思想就是用与自身问题相似但规模较小的问题来描述自己。递归算法的执行过程划分为递推和回归两个阶段。在递推阶段，把规模为n的问题的求解推到比原问题的规模较小的问题求解，且必须要有终止递归的条件。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到规模较大问题的解。就像打开一扇门里面还有一扇门，重复直到门里面没有门，然后再从一扇有一扇门中走出来。
（1）求解规模为n的问题可以转化为一个或多个结构相同、规模较小的问题，然后从这些小问题的解能方便地构造出大问题的解。相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)。
（2）递归调用的次数必须是有限的，每次递归调用后必须越来越接近某种限制条件。
（3）必须有结束递归的条件（边界条件）来终止递归。当递归函数符合这个限制条件时，它便不在调用自身，即当规模n=1时，能直接得解。
举个栗子：（全排列、组合、深度优先搜索等。在数据结构中，树、二叉树和列表常采用递归方式来定义。）
一堆产品中有一个次品存在，若这个次品与合格品的区别只是重量的不同，要找出这个次品。用递归法解时：先将这一堆产品分成个数一样的两堆。进行称重后必然有一端重一端轻，此时还无法判断次品所在；然后继续对每部分的n/2个产品再进行分组和称重，如果平衡则这部分的n/2个产品都为正品，即次品在另外那部分中，否则次品就在这n/2个产品中。这样寻找次品的范围就减少了一半。依照这种方法不断缩小次品的范围，直到最后一对一找出次品。
再来一个栗子
求阶乘问题：
详细说说递推和回归：
递推（时间复杂度计算）：
递推方程-->递归方程
计算递推式的方法：
1、迭代法
2、替换方法：猜递推式的解的范围（渐近复杂度的上下界），然后用数学归纳法证明是否存在满足条件的解。
3、公式法：
回归（应用举例）：
-
汉诺塔问题
把圆盘按大小顺序重新摆放在另一根柱子上：在三根柱子之间一次只能移动个圆盘。移动的时候始终只能小圆盘压着大圆盘。盘子只能在三个柱子上存放
#include<iostream>
using namespace std;
void move(int n,char x,char y)
{
cout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}
void Hannoi(int n,char A,char B,char C) //将n个盘子从A柱借助B柱移动C柱
{
if(n==1) //递归终止条件
move(1,A,C);
else
{
Hannoi(n-1,A,C,B); //递归调用
move(n,A,C);
Hannoi(n-1,B,A,C); //递归调用
}
}
int main()
{
int n;
cout<<”请输入盘子的个数：”<<endl;
cin>>n;
Hannoi(n,'A','B','C');
return 0;
}
经过分析得：
(1)将n个盘子上面的n-1个盘子借助C柱从A柱移到 B柱上，需要count（n-1）次；
(2)将A柱上第n个盘子移到C柱，花费1次；
(3)将B柱上的n-1个盘子借助A柱移到C柱，需要count（n-1）次；
移动次数也可用递归法计算：
#include <iostream>
using namespace std;
int main()
{
int num，count=0;
cout<<"请输入需要移动的盘子数目："<<endl;
cin>>num;
int val(int); //函数声明
if(num==0){
cout<<"输入的数字必须大于0!"<<endl;
return -1;
}
else
cout<<"需要"<<val(num)<<"次"<<endl;
return 0;
}
int val(int n){
int c;
if(n==1) c=1;
else c=2*val(n-1)+1;
return c;
}
-
斐波那契数列问题
求第n个数值
#include<iostream.h>
int fib(int n)
{
int f=0;
if(n==1) return 0;
if(n==2) return 1;
f=fib(n-1)+fib(n-2);
return f;
}
int main()
{
int n,i,m=0;
cin>>n;
m=fib(n);
cout<<"第"<<n<<"项是"<<m<<endl;
m=0;
for(i=1;i<=n;i++)
m=fib(i)+m;
cout<<"前"<<n<<"项和是"<<m<<endl;
return 0;
}
-
八皇后问题
在8×8格的国际象棋棋盘上放置八个皇后，使得任意两个皇后不能互相攻击，即任何行、列或对角线上不得有两个或两个以上的皇后。这样的一个格局称为问题的一个解。原文链接：[https://www.jianshu.com/p/65c8c60b83b8]
#include<iostream>
using namespace std;
const int Normalize=9; //定义常量，用来统一数组下标
int Num=0; //整型变量，记录方案数
int Queen[9]; //记录8个皇后所占用的列号
bool C[9]; //C[1]~C[8]布尔型变量，判断当前列是否可行
bool L[17]; //L[2]~L[16]布尔型变量，判断(i-j)对角线是否可行
bool R[17]; //R[2]~R[16]布尔型变量，判断(i+j)对角线是否可行
void check(int i) //被调用函数
{
int j; //循环变量，表示列号
int k; //临时变量
for(j=1;j<=8;j++)
{
if((C[j]==true) &&(R[i+j]==true)&&(L[i-j+Normalize]==true))
//表示第i行第j列可行
{
Queen[i]=j; //占用位置(i,j)
C[j]=false; //修改可行标志，包括所在列和两个对角线
L[i-j+Normalize]=false;
R[i+j]=false;
if(i<8) //判断是否放完8个皇后
{
check(i+1); //未放完8个皇后则继续放下一个
}
else //已经放完8个皇后
{
Num++; //方案数加1
cout<<"方案"<<Num<<":"<<"\t";//输出方案号
for(k=1;k<=8;k++)
cout<<k<<"行"<<Queen[k]<<"列"<<"\t";//输出具体方案
cout<<endl; //换行
}
C[j]=true; //修改可行标志，回溯
L[i-j+Normalize]=true;
R[i+j]=true;
} //循环结束
}
} //check函数结束
int main() //主函数
{
int i; //循环变量
Num=0; //方案数清零
for(i=1;i<9;i++) //置所有列可行
C[i]=true;
for(i=0;i<17;i++) //置所有对角线可行
L[i]=R[i]=true;
check(1); //递归放置8个皇后，从第一行开始放
return 0;
}
优缺点
优点：
处理重复性计算时，递归往往使函数的定义和算法的描述简单明了、易于理解、容易编程和验证。
缺点
递归的运算方法，决定了它的效率较低，一是数据要不断进出栈，另一就是存在大量的重复计算，这样使得应用递归时，输入的n值稍大，程序的求解就变得比较困难，故在有些情况下，递归可以转化为效率较高的非递归。
