汉诺塔？爬楼梯?斐波那契?知道递归就够了
*有远大志向而脚踏实地，有障碍失败而不言放弃，这样坚持下去，不会成功也会获益无穷——方海权*
@[toc]
# 导读
**我们在利用编程解决实际问题时总会遇到这样一种问题，即分解后的子问题与原问题类似，能用原来的方法解决问题，且最终的子问题是已知解或易于解，通常我们可以使用一种特殊的解决问题的方法——递归**
# 递归
其基本思想是：**将要解决的问题分解成比原问题规模小的子问题，当解决这个子问题时，又可以用到原问题的解决方法，按照这个原则逐步递推，最终将原问题转换成较小且已知的解的子问题。
递归一般分为两个阶段：**
## 递推
将**原问题不断地转化成子问题**， 逐渐从未知向己知推进， 最终到达已知解的问题，即递推阶段结束。
## 回归
从**已知解的问题**出发，按照递推的逆过程，逐一求值回归， 最后到达递归的开始处，即结束回归阶段，获得问题的解。
# 问题一般形式
诺可将求解问题逐步转化成与原问题类似的子问题，且最终子问题有明确的解，则可采用递归函数，实现问题的求解。
*注：由于在递归函数中存在着调用自身的过程，因此要控制反复进入自身的函数体调用，必须在函数体中设置终止条件，当条件成立时，终止调用自身，并使控制逐步返回到主调函数。*
# 爬楼梯问题：
**假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
解释：有两种⽅法可以爬到楼顶。
输⼊：n = 2
输出：2
第⼀种：1 阶 + 1 阶
第⼆种： 2 阶**
题解：这是一道非常经典的例题，通过分析我们不难发现一个这样的规律，当我们第一步只爬一个台阶剩下的n-1个台阶有它的爬法个数，当我们第一步爬两个台阶剩下的n-2个台阶就有它的爬法。以此类推最终我们就可以得到这样一个函数关系式：
这明显符合我们递归问题，因此我们可以写出代码：
```c
#include
int Class(int n) {
int i = 0;
if (n == 1)
return 1;
if (n == 2)
return 2;
return Class(n - 1) + Class(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
printf("%d", Class(n));
}
```
在我们运算过程中我们会发现总有那么几个数我们需要重复计算，大大的增加了我们的运算量，这里我们可以创造一张记忆表去记录我们已有的n：
```c
#include
int a[100] = { 0 };//创造记忆体
int b = 0;
int Class(int n)
{
int i = 0;
if (n == 1)
return 1;
if (n == 2)
return 2;
while (i <= b)
{
if (n == a[i])
return a[i];
}//判断楼梯阶数是否在记忆体中保留过
int c = Class(n - 1) + Class(n - 2);
a[b] = c;
return c;
}
int main()
{
int n;
scanf("%d", &n);
printf("需要爬%d", Class(n));
}```
当然这道题我们同样也可以使用一般循环的解法：
```c
#include
int Class(int n)
{
if (n == 1)
return 1;
if (n == 2)
return 2;
int c = 0;
int i = 0;
int pre = 2;
int prepor = 1;
for (i = 3;i <= n;i++)
{
c = pre + prepor;
prepor = pre;
pre = c;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
printf("需要爬%d", Class(n));
}
```
# 汉诺塔问题
**古代有一个梵塔，塔内有3个座A、B、C,开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上，有一个老和尚想把这64个盘子从A座移到C座，但每次只允许移动一个盘，且移动过程中在3个座上都始终保持大盘在下、小盘在上的状态。在移动过程中可以利用B座，要求编写程序并打印出移动的步骤。**
题解：将n个盘子从A座移到C座可以分解为以下三个步骤:
1. 将A座上n-1个盘子借助C座先移到B座上。
2. 将A座上剩下的一个盘子移到C座上。
3. 将n-1个盘子从B座借助A座移到C座上。
如果想将A座上3个盘子移到C座上，可以分解为以下三个步骤:
4. 将A座上2个盘子借助C座移到B座上
5. 将A座上1个盘子移到C座上;
6. 将B座上2个盘子借助A座移到C座上。
其中第(2)步可以直接实现。第(1)步又可用递归方法分解为:
1. 将A座上1个盘子从A座移到C座
2. 将A座上1个盘子从A座移到B座
3. 将C座上1个盘子从C座移到B座
4. 将B座上1个盘子从B座移到A座上
5. 将B座上1个盘子从B座移到C座上
6. 将A座上1个盘子从A座移到C座上。
综合以上情况，可得到移动3个盘子的步骤为:
A→C, A→B，C→B，A→C，B→A，B→C，A→C
代码如下：
```c
#include
void Hanoi(int n, char A, char B, char C)
{
if (n == 1)
printf("%c->%c\n", A, C);
else
{
Hanoi(n - 1, A, C, B);
printf("%c->%c\n", A, C);
Hanoi(n - 1, B, A, C);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
Hanoi(n, 'A', 'B', 'C');
return 0;
}
```
运行结果如下：
