汉诺塔问题是个非常著名的问题但很多教材对其解法都是直接略过很是遗憾。在这里将深度解决这个问题。递归的两大要素终止条件和循环要素。递归要成功离不开两点一是递归递进机制二是递进终止条件。递进机制应保证每次调用都向终止条件靠近一步。这就保证递归能够正常结束不至于出现无限循环导致系统内存耗尽而崩溃。案例计算一个数的阶乘1*2*3*4*5…………*n#includestdio.hintgo(intn){if(n1){return1;}else{returnn*go(n-1);}}intmain(){printf(%d\n,go(5));return0;}递归调用中每次函数调用都有一定的堆栈操作相比循环方式时空开销较大因此递归函数的效率总比功能相同的循环结构更低递归编写的函数尽量用循环代替以提高效率。如果用循环语句实现的算法要比使用递归复杂得多此时建议采用递归方式。任何循环都可以转化为递归不是任何递归都可以转化为循环简而言之追求程序运行速度尽量少用递归。追求代码简洁尽量使用递归。循环递归一定能实现递归循环不一定能实现。Hanoi汉诺塔问题古代有一个梵塔塔内有3个座A、B、C开始时A座上有64个金盘金盘大小不等大的在下小的在上。有一个老和尚想把这64个金盘从A座移动到C座但规定每次只允许移动一个盘且在移动过程中在3个座上都始终保持大盘在下小盘在上。在移动过程中可以利用B座。要求编程输出移动盘子的步骤。据说移动完成就是世界的末日。分析有三个盘1、2、3的情况下要把3移动到C就要先把1和2移动B(需要3次)再把3移动到C需要一次再把1和2移动到C需要3次因此go(3)go(2)1go(2)2*go(3-1)1 [假设go为递归函数名]其思想就是把n-1个盘子当作一个整体先移动到B再把第n个盘子移动到C再把n-1移动到Cn-1n-----n n-1 //需要go(n-1)次n-1 n //需要1次n-1n //需要go(n-1)次代码如下#includestdio.hintgo(intn){if(n1){return1;}else{return2*go(n-1)1;}}intmain(){intigo(3);printf(%d\n,i);return0;}补充上面的递归方法也可以用for循环实现#includestdio.hunsignedlonglonggo(intn){if(n1){return1;}else{return2*go(n-1)1;}}intmain(){unsignedlonglonga11;unsignedlonglonga2,j;int i;for(i1;i5;i){//用for实现a22*a11;a1a2;}jgo(5); //用递归实现printf(%llu\n,j);printf(%llu\n,a2);return0;}效果如下当参数为64时需要移动18446744073709551615次约1844亿亿次如果1秒移动一个盘子需要584942417355.07203243911719939117年约5849亿年。