作为一种易于简化工作的思想方法，递归思想有时也应用于编程中以解决一些问题。
汉诺塔问题和青蛙跳台阶问题是函数递归中的经典问题。
汉诺塔问题
是什么？
汉诺塔问题起源于古印度。
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
怎么做？
若有3个盘子，手动移动，则移动步骤可以如下：
1.A->C
2.A->B
3.A->B
4.A->C
5.A->B
6.A->C
7.A->C
//共有七个步骤
运用“大事化小”的递归思想，以上7步实际上可以简化为以下步骤：
即先将1、2号盘以C为媒介移动到B盘，具体移动步骤暂不考虑；再将1号盘移动到C盘；最后将1、2号盘以A为媒介从B移动到C，具体移动步骤暂不考虑。
现在有这样一个问题：
输入一个数n，代表A上要移动的盘数，输出最少的移动步骤。
思考和推广：
类比上面对3个盘的问题的分析，将盘从上到下依次标号为1到n，可以将移动n个盘简化为以下步骤：
1.将1到n-1号盘以C为媒介从A移动到B
2.将第n号盘从A移动到C
3.将1到n-1号盘以A为媒介从B移动到
有了以上的思路，可以写出代码如下：
#include<stdio.h>
void swap(char x, char y)
{
printf("%c->%c\n", x, y);
}
void Hanoi(int n,char a,char b,char c)
{
if (n<=1)
{
swap(a, c);//交换
}
else
{
Hanoi(n - 1, a, c, b);//将1到n-1号盘以C为媒介从A移动到B
swap(a, c);//将第n号盘从A移动到C
Hanoi(n - 1, a, b, c);//将1到n-1号盘以A为媒介从B移动到C
}
}
int main()
{
int n;
printf("请输入层数:>");
scanf("%d", &n);
Hanoi(n, 'A', 'B', 'C');
return 0;
}
该递归的限制条件为n<=1,n==1时递推结束。
该代码的输入和输出如下：
青蛙跳台阶问题
一个问题
有一只青蛙和n个台阶，青蛙一次能跳1个或2个台阶，青蛙要跳完这个n个台阶，共有多少种跳法？
思考和推广：
··若有1个台阶，则只有一种跳法
··若有两个台阶，则可以一次跳一阶，或者直接跳两阶，即有两种跳法
··若有n个台阶，则可以先考虑第一次跳。第一次只有两种选择：
1.跳一阶
2.跳两阶
·若第一次跳一阶,则还剩n-1个台阶
·若第一次跳两阶，则还剩n-2个台阶
-假设n-1个台阶的跳法数量为a，n-2个台阶的跳法数量为b，则n个台阶的跳法数量为a+b
-则只需计算n-1个台阶的跳法数量和n-2个台阶的跳法数量，这又回到了刚才的情形。
怎么做？
·递归
用递归思想编程解决
#include<stdio.h>
int frog(int n)
{
if (n==1)//若台阶数为1，则跳法只有一种
{
return 1;
}
else if (n == 2)//若台阶数为2，则跳法只有两种
{
return 2;
}
else
{
return frog(n - 1) + frog(n - 2);//a+b
}
}
int main()
{
int n;
printf("请输入台阶数>:");
scanf("%d", &n);
int ret = frog(n);
printf("共有%d种跳法\n", ret);
return 0;
}
该递归的限制条件为n==2,满足该限制条件时递推结束。
·迭代
通过列出计算结果，可以得到如下数列：
1 2 3 5 8 13 21 34 55 ...
发现其与斐波那契数列非常相似（1 1 2 3 5 8 13 21 34 . . .）
则也可以选择迭代法求取结果
#include<stdio.h>
int frog(int n)
{
int a = 0;
int b = 1;
int c = 0;
if (n==1)
{
return 1;
}
else
{
for (int i = 0; i < n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
}
int main()
{
int n;
printf("请输入台阶数>:");
scanf("%d", &n);
int ret = frog(n);
printf("共有%d种跳法\n", ret);
return 0;
}
一个拓展：变态青蛙跳台阶问题
一只青蛙可以一次跳1个台阶，也可以跳2个台阶，......也可以跳n个台阶。求青蛙跳上n级台阶共有多少种算法。
/*
每个台阶可以看作一块木板，让青蛙跳上去，n个台阶就有n块木板，最后一块木板是青蛙到达的位子， 必须存在，
其他 (n-1) 块木板可以任意选择是否存在，则每个木板有存在和不存在两种选择，(n-1) 块木板 就有 [2^(n-1)] 种跳法，
可以直接得到结果。
其实我们所要求的序列为：0,1,2,4,8,16,……
*/
#include<stdio.h>
int Jump(int n)
{
if (n==0 || n==1)
{
return n;
}
else
{
int num = 1;
for (int i = 1; i < n; i++)
{
num = num * 2;
}
return num;
}
}
int main()
{
int n;
while (scanf("%d",&n) != EOF)
{
int ret = Jump(n);
printf("%d\n", ret);
}
return 0;
}
