一.递归问题的处理步骤
1）抽象出递归公式：对实际问题进行部分穷举，抽象出递归关系（关键），并列出“递归表达式”
2）确定递归出口：找出递归调用终止点
二.菲波那契数列
实际问题：兔子繁殖问题
兔子在出生一个月后为成兔，两个月后就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有
兔都不死，那么一年以后可以繁殖多少对兔子？
1）抽象出递归公式
初始为：1对幼兔
第n个月 1 2 3 4 5 6 7
幼兔： 1 0 1 1 2 3 5
成年兔： 0 1 1 2 3 5 8
总计： 1 1 2 3 5 8 13
规律：
幼兔=前一个月成年兔
成年兔=前一个月成年兔+前一个月幼兔
总计=幼兔+成年兔=前一个月成年兔+（前一个月成年兔+前一个月幼兔）
=前一个月成年兔+前一个月总计
=（再前一个月成年兔+再前一个月幼兔）+前一个月总计
=再前一个月总计+前一个月总计
递归表达式如下：
A(1)=A(2)=1，
A(N)=A(N-1)+A(N-2)（N>=3）
2）找出递归调用终止点
由递归表达式很明显观察出，递归终止点为3；故剩下的A(1),A(2)直接穷举出来即可
一年后，相当于“第13个月”。
代码如下：
1 #include<iostream> 2 using namespace std; 3 4 int Fibonacci(int X) 5 { 6 if(X==1||X==2) 7 { 8 return 1; 9 } 10 else 11 { 12 return(Fibonacci(X-1)+Fibonacci(X-2)); 13 } 14 } 15 16 int main() 17 { 18 int tempInt; 19 int returnInt; 20 21 tempInt=13; 22 returnInt=Fibonacci(tempInt); 23 24 cout<<returnInt<<endl<<endl; 25 system("pause"); 26 return 0; 27 28 }
运行结果：
三.汉诺塔
http://blog.163.com/liuknan@yeah/blog/static/16983829020109892141485/