我们学习函数递归和迭代往往需要掌握许多的数学规律，公式定律，下面我们通过两个递归，迭代相关的经典例题来了解递归和迭代的思想。
今天的主角是我们的汉诺塔和青蛙跳台阶。
（1）汉诺塔：相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
分析：对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但我们可以利用下面的方法来解决。设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：
(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；
(2)将A杆中剩下的第n号盘移至C杆；
(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。
这样问题解决了，但实际操作中，只有第二步可直接完成，而第一、三步又成为移动的新问题。以上操作的实质是把移动n个盘子的问题转化为移动n-1个盘，那一、三步如何解决？事实上，上述方法设盘子数为n, n可为任意数，该法同样适用于移动n-1个盘。因此，依据上法，可解决n -1个盘子从A杆移到B杆(第一步)或从B杆移到C杆(第三步)问题。现在，问题由移动n个盘子的操作转化为移动n-2个盘子的操作。依据该原理，层层递推，即可将原问题转化为解决移动n -2、n -3… … 3、2，直到移动1个盘的操作，而移动一个盘的操作是可以直接完成的。至此，我们的任务算作是真正完成了。而这种由繁化简，用简单的问题和已知的操作运算来解决复杂问题的方法，就是递归法。在计算机设计语言中，用递归法编写的程序就是递归程序。
假设只有两个盘子分析过程
这样我们可以分析出
//汉诺塔问题
#include<stdio.h>
int count=0;//记录移动次数
void fun(int n,char A,char B,char C) //A,B,C分别是起始，辅助，目标
{
if(n>0)
{
fun(n-1,A,C,B);//假定n-1个为整体
count++;
printf("%c-->%c\n",A,C);//将下面n-1个盘从A移动到C
//再将最上面一个从A移动到B
fun(n-1,B,A,C);//最后将B三的移动到C
}
}
int main()
{
int n;
char A='A';
char B='B';
char C='C';
printf("输入盘子数量：");
scanf("%d",&n);
fun(n,A,B,C);
printf("至少需要移动%d次\n",count);
return 0;
} 过程如下：
输入盘子数量：3
A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C
至少需要移动7次
--------------------------------
Process exited after 1.719 seconds with return value 0
请按任意键继续. . .（2）青蛙跳台阶
有一只青蛙跳台阶，有n级台阶，青蛙一次可以跳1级台阶，也可以跳2级台阶；问：该青蛙跳到第n级台阶一共有多少种跳法。
思想：可以先列举1，2，3，4，5个台阶的跳法，自己画图理解即可
可以得出如下递归关系：
int fun1(int n)//递归
{
if(n<=1)
return 1;
else
return fun1(n-1)+fun1(n-2);//公式类似于斐波那契数列
}
int main()
{
int n,count;//n为台阶数量,count记录跳法
printf("输入台阶数\n");
scanf("%d",&n);
count=fun1(n);
printf("一共有%d种跳法\n",count);
return 0;
}运行如下：
输入台阶数
5
一共有8种跳法
--------------------------------
Process exited after 2.358 seconds with return value 0
请按任意键继续. . .下面我们继续分析，既然这个问题类似与斐波那契数列问题，我们是不是也可以迭代？
如下分析：
#include<stdio.h>
int fun2(int n)//迭代
{
int a=1,b=2,c=3;
if(n==1)//1，2的情况例外
return 1;
if(n==2)
return 2;
else{
while(n>2){//类似斐波那契的迭代，注意循环条件
c=a+b;
a=b;
b=c;
n--;
}
return c;
}
}
int main()
{
int n,count;//n为台阶数量,count记录跳法
printf("输入台阶数\n");
scanf("%d",&n);
count=fun2(n);
printf("一共有%d种跳法\n",count);
return 0;
} 这里结果一样
输入台阶数
5
一共有8种跳法
--------------------------------
Process exited after 2.358 seconds with return value 0
请按任意键继续. . .最后回过头想想有没有了解到递归和迭代的使用技巧
试试这题：有一只青蛙跳台阶，有n级台阶，青蛙一次可以跳1，2，3，.......，n级台阶；问：该青蛙跳到第n级台阶一共有多少种跳法？