1.递归篇

1.1 递归求斐波那契数列

#include<iostream>

using namespace std;

//递推法求斐波那契数
//需要将中间值进行存储

const int MAXN = 35;

int fibonacci[MAXN];    //存储斐波那契数

void Initial(){
	fibonacci[0] = 0;
	fibonacci[1] = 1;
	for(int i = 2; i < MAXN; ++i){
		fibonacci[i] = fibonacci[i -1] + fibonacci[i - 2];
	}
}

int main(){
	Initial();
	int n;
	while(scanf("%d",&n) != EOF){
		printf("%d\n",fibonacci[n]);
	}
	return 0;
}

1.2 递归求n的阶乘

#include<iostream>

using namespace std;

long long Fact(int n) {
	if(n == 0) {
		return 1;
	}
	return n*Fact(n-1);

}

int main() {
	int n;
	while(scanf("%d",&n) != EOF){
		printf("%lld\n",Fact(n));
	}
}

1.3 递归之汉诺塔问题

#include<iostream>

using namespace std;

//普通汉诺塔问题
long long Hanoi(int n){
	if(n == 1){
		return 1;
	}else{
		return 2 * Hanoi(n -1) + 1;
	}
}

//汉诺塔III
//不允许将圆盘从最左边移动到最右边
long long Hanoi_3(int n) {
	if(n == 1) {
		return 2;
	} else {
		return 3 * Hanoi_3(n-1) + 2;
	}
}

int main() {
	int n;
	while(scanf("%d",&n) != EOF) {
		printf("%lld\n",Hanoi_3(n));
	}
}