从汉诺塔问题看递归

本文章是我在读研期间，第一篇文章，与其说是博客，不如说是博主为了不虚度这研究生生活的一种监督。之前博主写学习qt的时候很喜欢浏览大神的博客，例如一去二三里，现在我也想通过博客记录自己的成长。由于博主水平真的很低，不能给大家提供什么有效的帮助，再次表示歉意。

看《数据结构，算法与应用c++语言描述》一文中第185页出现了一个汉诺塔问题。这是个递归问题，想了好久终于在今天想懂了一点点（用起来说实在的还是蒙蒙的）。

看递推问题让我想到了考研问题的数学归纳法，感觉基本上一个套路，首先我先附上代码让大家有些概念，我们根据代码来推一遍这个函数，慢慢习惯了这个思路就可以了。

首先要明确一个问题，递归函数需要有个范围，不然就进入无限死循环中。这里我们主要对move函数进行讲解。

我们的目的是将盘子通过A盘子，转换到C盘子。

当 n =2 时 ，我们首先执行move（2，‘a’,'b','c'）;

因为 n != 1 说以又将执行一遍 move(1,'a','c',b');(注意这里并不是a到c了，是a到b)；

这时将a移动到b完成，接着返回，执行 move（2,'a','b','c'）中的第三条指令，将a移动到c，

接下来将执行move(2,'a','b','c');中的第4条指令，此时接着调用move（1,'b','a','c'）将b移动到c上；

返回执行完成。所用实际步骤是3步。

当n = 3 时，同理我们首先要执行move(3,'a','b','c');

因为n ！= 1将执行move（2，‘a’，‘c’，‘b’）；

因为n!= 1又将执行move（1,'a','b','c'）;

这时n =1 将a移动到C ；返回至move（2,'a’,'c','b'）;

接下来接着move（2，‘a’，‘c’，‘b’）后面的步骤3，将a移动到b

接下来只想move （2，‘a’,'c','b'）;调用move(1,'c','a','b')，将a移动至c;

再调回至move（3，a,b,c）;再按步骤执行后面那部分。

这么看实在是麻烦，根据数据结构中树的原理，我个人总结了贴吧上都没有的递推方法（因为第一次用没有找到怎么上传图片的功能，所以只能把思路说说）。

首先move（3,a,b,c）有三个分支，move(2,a,c,b)      cout << a ---- c   move(2,b,c,a);再继续对每个节点继续分，直至n =1 ;

梳理流程上，采用后序遍历的方法，对每个节点叶子采用从左向右的顺序方法遍历，再访问根节点。

根据数学归纳法的说明证明 n = 1 ，2 时成立 当 n 大于2时的某点也成立，那么  所有的n都成立 ，所以成立。

所以针对这move函数我们总结出

若想将数据根据堆栈的方法从a移动到c上，就要先将a通过c移动到b上，将a移动到c上，再由b通过a移动到c上的方法。

当然跳出该问题，我们还可以看到其他的问题，例如有7个层的话如何将之从A移动到C上呢？我们根据数学归纳法来解决，当只有一层时我们只需要1步将A移动到C。如果有两个旗子呢，我们将A中前1个旗子移动到B上，再将最后一个移动到C上，再将B移动到c上，需要1+1+1 =3步。3个的话我们先将前两个从A移动到B，再将A最后一个移动到C，再将B上的移动到C，算数变成了3+3+1 = 7 ,所以推出四个旗子有7+7+1 =15 步 ，5个旗子有 15+15 +1 =31 步最短的步骤。

最后

以上就是震动钻石为你收集整理的从汉诺塔问题看递归的全部内容，希望文章能够帮你解决从汉诺塔问题看递归所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。