递归_递归算法必须具备的两个条件

基本思想：
递归策略只需要少量的代码就可以描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。一般来说，构成递归需要具备以下两个条件：首先，子问题和原始问题要执行的操作应该是一致的，并且通常来说，子问题规模更小，更为简单；其次，不能无限制地调用自身，需要有一个出口，化简为非递归的情况进行处理。

斐波那契数列是一个比较典型的递归的例子，它指的是这样一个数列：0,1，1,2,3,5,8,13,21…。在数学上，斐波那契数列以如下方式定义：F[0]=0,F[1]=1,F[N]=F[N-1]+F[N-2],(N>=2,N为整数）。根据其定义可以看出，当N>=2时，数列的每一项都等于前两项之和。也就是说，如果要求出数列的第N项，只需要先求出数列第N-1项和第N-2项，然后再把第N-1项和第N-2项相加就可以了；而要求出第N-1项和第N-2项，需要知道第N-2项、第N-3项和第N-3项和第N-4项；这样依次递归下去，求解问题的规模是在不断减小的。直到第1项和第0项可以直接由定义直接得到，然后所需要的求解的项就可以依次解得了。实际上，递归往往可以使得算法的描述更加简洁且易于理解。

但是，思路简洁所带来的代价是运行效率的降低。递归算法解题相对常用的算法如普通循环等，运行效率是比较低的。在递归调用的过程中，系统为每一层的返回点，局部变量等开辟了栈来储存。递归次数过多，容易造成栈的溢出。因此，应该尽量避免使用递归，除非没有更好的算法，或者在某种特定情况下递归更为合适。

斐波那契数列POJ2753

问题描述：
斐波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来每个数都等于前两个数之和。给出一个整数a，要求斐波那契数列中第a个数是什么。
输入数据：
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占一行，包括一个正整数a(1<=a<=20)。
输出要求：
输出有n行，每行输出对应一个输入。输出应是一个整数，为斐波那契数列的大小。
输入样例：
4
5
2
19
1
输出样例：
5
1
4181
1

#include <iostream>
#include <algorithm>
using namespace std;
int sum;
int f(int x) {
   
	if(x<=2)
		return 1;
    return f(x-1)+f(x-2);
}
int main() {
   
	int n;
	cin>>n;
	while(n--) {
   
		int t;
		cin>>t;
		cout<<f(t)<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

其实这道问题不用递归也可以写出来，对于刚学习C语言的同学来说难度应该不是很大。以下是不用递归写的代码：

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
   
	int t;
	cin>>t;
	while(t--){
   
		int n;
		cin>>n;
		int a[100];
		a[1]=1;
		a[2]=1;
		for(int i=3;i<=n;i++){
   
			a[i]=a[i-1]+a[i-2];
		}
		cout<<a[n]<<endl;
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在没有接触递归的时候，不知道你们有没有和我一样，接触过这样两道题，求最大公因数问题和和公倍数问题，我记得我当初做的是最大公因数问题，在我们学校OJ平台，一直错误%50，过不去，记忆犹新是因为那天还有十几分就是新年了，果然它成了2020年的遗憾。哈哈哈哈，跑偏了。

其实，解那道题，是开始的思路错了，学长当时说的辗转相除法我百度了也不是很理解，所以说啊，不会的问题一定要放一放，就像我，现在不就懂了，哈哈哈哈哈哈，一堆废话。

求最大公约数问题POJ3248

问题描述：
给定两个整数，求它们的最大公约数问题。

输入数据：
输入一行，包含两个正整数（<1 000 000 000）。

输出要求：
输出一个正整数，即这两个正整数的最大公约数。

输入样例：
6 9

输出样例：
3

求最大公约数问题可以使用辗转相除法。假设a>b>0，那么a和b的最大公约数等于b和a%b的最大公约数，然后把b和a%b作为新的一轮的输入。由于这个过程会一直递减，知道a%b=0时，b的值就是所要求的最大公约数。9和6的最大最大公约数等于6和9%6=3的最大公约数。由于6%3=0，所以最大公约数为3。看到这里有没有这个思想很像递归，但是看代码的话，就是只用循环就可以了。

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
   
	int x;
	cin>>x;
	while(x--){
   
	int n,m;
	cin>>n>>m;
	int t;
	if(n>m){
   
		t=n;
		n=m;
		m=t;
	}
	int r; 
	while(m!=0){
   
		r=n%m;
		n=m;
		m=r;
	}
	cout<<n<<endl;
}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

分解因数POJ2749

问题描述：
给出一个正整数a,要求分解成若干个正整数的成积，即a=a1 X a2 X a3 X…an,并且1<=a1<=a2<=a3<=…<=an,问这样的分解有多少种。注意：a=a也是一种分解。
输入数据：
第一行是测试数据的组数n，后面跟着n行输入。每组测试数据占一行，包含一个正整数a(1<a<32 768)。
输出数据：
输出为n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数。
输入样例：
2
2
20
输出样例：
1
4

#include <iostream>
#include <algorithm>
using namespace std;
int c;
void f(int a,int n) {
   
	for(int i=a; i<n; i++) {
   
		if(n%i==0&&i<n/i) {
   
			c++
1
2
3
4
5
6
7
8
9
10