递归：斐波那契数列、递归实现指数型枚举、递归实现排列型枚举

递归：O(2^n)

        调用自己

例题及代码模板：

斐波那契数列

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从 0 开始，第 0 项为 0。

数据范围

0≤n≤39

样例

输入整数 n=5 返回 5

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;int Fibonacci(int n){if(n==0) return 0;if(n==1) return 1;if(n==2) return 1;return Fibonacci(n-1)+Fibonacci(n-2);
}
int main(){int n;cin>>n;cout<<Fibonacci(n)<<endl;return 0;
} 

O(n*2^n)

递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：

3

输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=15;
int n;
int st[N];
void dfs(int u){if(u==n){for(int i=0;i<n;i++){if(st[i]==1)cout<<i+1<<" ";}cout<<endl;return ;}st[u]=2;dfs(u+1);st[u]=0;st[u]=1;dfs(u+1);st[u]=0;
}int main(){cin>>n;dfs(0);	return 0;
}

递归实现排列型枚举

把 1∼n这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n。

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤9

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 时间复杂度：

                一共递归n层:

                        第一层是：O(n)

                           第二层：有n个分支，每个分支有一个for循环，即O(n*n)

                           第三层：有n*(n-1)个分支，每个分支有一个for循环，即O(n*(n-1)*n)

                            ……

                           第n层（叶节点）：有n！个分支，每个分支有一个for循环，即O(n!*n)

                        所以总的时间复杂度为：n(1+n+n(n-1)+……+n!)

                        (1+n+n(n-1)+……+n!)等价于：（n!+n!/1+n!/(1*2)+n!/(1*2*3)+……+n!/(n-1)!+n!/n!）；首先这个等式一定大于n!且小于（n!+n!/1+n!/2+n!/4+……+n!/2^(n-1)+n!/2^n）即3n!

                        所以这道题的时间复杂度为O（3n*n!）,即O(n*n!)

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10;
int n,state[N];
bool used[N];
void dfs(int u) {if(u>n) {for(int i=1; i<=n; i++)cout<<state[i]<<" ";cout<<endl;return ;}for(int i=1; i<=n; i++) {if(!used[i]) {state[u]=i;used[i]=true;dfs(u+1);state[u]=0;used[i]=false;}}
}
int main() {cin>>n;dfs(1);return 0;
}

递归实现组合型枚举

带分数