算法描述：
递归问题都可以先画出一个递归搜索树，然后再转换成代码！
例题：
1.Acwing 819. 递归求阶乘
#include<iostream>
using namespace std;
int fact(int n)
{
if(n==1) return 1;
return n*fact(n-1);
}
int main()
{
int n;
cin>>n;
cout<<fact(n);
return 0;
}
2.AcWing 820. 递归求斐波那契数列
#include<iostream>
using namespace std;
int fib(int n)
{
if(n==1||n==2) return 1;
else return fib(n-1)+fib(n-2);
}
int main()
{
int n;
cin>>n;
cout<<fib(n);
return 0;
}
其实用递归的效率是很低的，因为它同一个数值要算好多遍，所以用递归时也要考虑范围，这个题最大是30，还可以，当是42时，就超时了。
3.AcWing 821. 跳台阶
#include<iostream>
using namespace std;
int n,cnt=0;
void f(int k)
{
if(k==n) cnt++;
else if(k<n){
f(k+1);
f(k+2);
}
}
int main()
{
cin>>n;
f(0);
cout<<cnt;
}
4.AcWing 822. 走方格
刚开始的思路:
#include<iostream>
using namespace std;
int n,m,sum;
void f(int x,int y)
{
if(x==n&&y==m) sum++;
else if(x<n&&y<m){
f(x,y+1);//右移；
f(x+1,y);//下移；
}
}
int main()
{
cin>>n>>m;
f(0,0);
cout<<sum;
return 0;
}
这样不管输入任何值，都是输出0;但又觉着思路没什么问题。所以就看了y总的讲解。
#include<iostream>
using namespace std;
int n,m,sum;
int dx[]={0,1},dy[]={1,0};//右移或者左移
void f(int x,int y)
{
if(x==n&&y==m) sum++;
else{
if(y<m) f(x+dx[0],y+dy[0]);//右移；
if(x<n) f(x+dx[1],y+dy[1]);//下移；
}
}
int main()
{
cin>>n>>m;
f(0,0);
cout<<sum;
return 0;
}
看完后发现这两个else if一样啊，越想越一样。于是去求助别人，找到了问题所在。假设当n=2，m=3时，当执行到n=2，m=2时，在我想来，接下来会y+1，但其实不是，因为不满足x<n&&y<m，这样就会返回，所以当执行到最后（2，3）的前一步时都会返回，不会再继续往下执行了，sum不会++，所以就是0了。问题是自己推了好几遍，都默认能执行到2，3.可能陷入了思维定势了叭，让别人一看就看出来了。那么第一个思路要怎么改呢！
#include<iostream>
using namespace std;
int n,m,sum;
void f(int x,int y)
{
if(x==n&&y==m) sum++;
else if((x<=n&&y<m)||(x<n&&y<=m)){
f(x,y+1);//右移；
f(x+1,y);//下移；
}
}
int main()
{
cin>>n>>m;
f(0,0);
cout<<sum;
return 0;
}
这样就ok了.
5.AcWing 823. 排列
刚开始思路:
#include<iostream>
using namespace std;
int n;
bool b[10]={0};
void f(int cnt){
if(cnt==n) cout<<endl;
else if(cnt<n){
for(int i=1;i<=n;++i){
if(!b[i])
cout<<i<<" ";
b[i]=true;
//cnt++;
f(cnt+1);
b[i]=false;
}
}
}
int main()
{
cin>>n;
f(0);
return 0;
}
但就是运行不出来，调试了一会也出不来，于是看了y总的代码：
#include<iostream>
using namespace std;
const int N=10;
int n;
void dfs(int u,int nums[],bool st[])
{
if(u>n){
for(int i=1;i<=n;++i)
cout<<nums[i]<<" ";
cout<<endl;
}
else
{
for(int i=1;i<=n;++i)
if(!st[i]){
nums[u]=i;
st[i]=true;
dfs(u+1,nums,st);
st[i]=false;
}
}
}
int main()
{
cin>>n;
int nums[N];
bool st[n]={0};
dfs(1,nums,st);
return 0;
}
y总是先把每个数存到nums数组中，然后等存满了就输出，我是想着用i来输出，但没找到错在哪，于是照着y总的改了改，但还是不行，后边再回来看吧
#include<iostream>
using namespace std;
const int N=10;
int n;
void dfs(int u,bool st[])
{
if(u>n)
cout<<endl;
else
{
for(int i=1;i<=n;++i)
if(!st[i])
{
st[i]=true;
cout<<i<<" ";
dfs(u+1,st);
st[i]=false;
}
}
}
int main()
{
cin>>n;
int nums[N];
bool st[n]={0};
dfs(1,st);
return 0;
}
上面y总的nums[]和st[]是局部变量，下面是全局变量:
#include<iostream>
using namespace std;
const int N=10;
int n;
int nums[N];
bool st[N]={0};
void dfs(int u)
{
if(u>n){
for(int i=1;i<=n;++i)
cout<<nums[i]<<" ";
cout<<endl;
}
else
{
for(int i=1;i<=n;++i)
if(!st[i]){
nums[u]=i;
st[i]=true;
dfs(u+1,nums,st);
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
所以在dfs，bfs中数组定义还是全局变量的好，这样函数的参数就能少一点.
6.AcWing 92. 递归实现指数型枚举
这个题思路很多，一个是可以把每个1~n每个数都列出来，然后考虑每个数要不要选
#include<iostream>
using namespace std;
int n;
const int N = 16;
int st[N];
void dfs(int u)
{
if(u>n){
for(int i=1;i<=n;++i)
if(st[i]==1)
cout<<i<<" ";
cout<<endl;
return;
}
else
{
st[u]=1;//第一个分支，选
dfs[u+1];
st[u]=0;//恢复现场
st[u]=2;//第二个分支，不选
dfs[u+1];
st[u]=0;
}
}
int main()
{
cin>>n;
dfs(1);
}
下面再说一下这个题的其他思路:
#include<iostream>
using namespace std;
int n;
void dfs(int u,int state)
{
if(u==n)
{
for(int i=0;i<n;++i)
if(state >> i & 1)
cout << i+1<<' ';
cout<<endl;
return;
}
dfs(u+1,state);
dfs(u+1,state|1<<u);
}
int main()
{
cin>>n;
dfs(0,0);//位运算，用二进制数表示一个集合，1的话表示存在，0的话表示不存在
return 0;
}
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> path;
void dfs(int u,int state)
{
if(u==n)
{
for(auto x : path) cout<<x<<" ";
cout<<endl;
return;
}
for(int i=0;i<n;++i)
if(!(state>>i&1))
{
path.push_back(i+1);
dfs(u+1,state | (1<<i));
path.pop_back();
}
}
int main()
{
cin>>n;
dfs(0,0);
return 0;
}
过了一段时间又做这个题:
#include<iostream>
using namespace std;
const int N = 15;
int st[N];
int nums[N];//用不到
int n;
void dfs(int m)
{
if(m>n){
for(int i=1;i<=n;++i)
if(!st[i])
cout<<i<<" ";
cout<<endl;
}
st[m]=false;
dfs(m+1);
st[m]=true;
dfs(m+1);
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
运行显示”Segmentation Fault”,什么也不输出
#include<iostream>
using namespace std;
const int N = 15;
int st[N];
int nums[N];//用不到
int n;
void dfs(int m)
{
if(m>n){
for(int i=1;i<=n;++i)
if(!st[i])
cout<<i<<" ";
cout<<endl;
}
else{
st[m]=false;
dfs(m+1);
st[m]=true;
dfs(m+1);
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
但是添加上else后就ac了…
7.凑算式 蓝桥杯2016初赛
这个题可以用暴力枚举，但很大概率会超时，这题也可以用递归来做，用递归的话中心思想就是上边的全排列问题的代码
#include<iostream>
using namespace std;
const int N = 10;
int num[N];
bool st[N];
int cnt=0;
void dfs(int step)
{
if(step>=N){
if(num[1]+1.0*num[2]/num[3]+(1.0*num[4]*100+num[5]*10+1.0*num[6])/(num[7]*100+num[8]*10+num[9])==10.0)
{
// for(int i=1;i<N;++i)
// cout<<num[i]<<" ";
// cout<<endl;
cnt++;
}
}
else
{
for(int i=1;i<N;++i)
if(!st[i]){
st[i]=true;
num[step]=i;
dfs(step+1);
st[i]=false;
}
}
}
int main()
{
dfs(1);
cout<<cnt;
return 0;
}
