汉诺威递归算法分析过程
汉诺威：汉诺威(也叫汉诺威)问题是一种基于印度古老传说的益智玩具。 梵天创造世界时制作了三根钻石柱子，在一根柱子上从下到上按大小顺序堆积了64枚黄金圆盘。 梵天命令mndmj将圆盘从下到上按大小顺序重新排列在另一根柱子上。 而且，小圆盘不能使圆盘变大，在三个柱之间一次只能移动一个圆盘。
不管这个传说的真实性有多大，请考虑把64个黄金圆盘从一个柱子转移到另一个柱子上，始终保持从上到下的大顺序。 这个需要移动几次？ 一个的时候当然用了一次，两个的时候用了三次，三个的时候用了七次……这个真的累了。 这里需要递归方法。 假设有n张，移动次数为f(n ) .很明显
f(1)=1，f ) )2)=3，f(3)=7，并且f ) k1 )=2f ) k ) 1。 随后很容易证明f(n )=2^n-1。
在n=64的情况下，
如果是每秒一次的话，一共需要多长时间？ 一个常年365天为31536000秒，闰年366天为31622400秒，平均每年为31556952秒。 计算一下：
18446744073709551615秒
这表明移动这些黄金圆盘需要5845亿5400万年以上，但据说地球存在只有45亿年，太阳系的预期寿命也只有几百亿年。 真正的5845亿5400万年过去了，太阳系、银河系自不必说，至少地球上的所有生命，连同梵塔、寺庙等，早已灰飞烟灭。
汉诺威问题在数学界有很高的研究价值，至今仍被一些数学家们研究，也是我们喜欢的智力游戏。 那有助于智力的开发和思维的活跃。
我以前看到了经典的递归代码。 几行简单的代码就解决了一个深刻的问题。 为什么在那几行代码中就解决了汉诺威问题呢？
代码如下所示。
看了这个程序，很难理解的是以下两个句子。
move(n-1，a，c，b ) ) ) )。
move(n-1，b，a，c ) )。
你会发现你在使用递归。 第一句将第一个位置的磁盘移动到第二个位置，第二句将第二个位置移动到第三个位置。 但是，为什么这样可以递归地给出答案呢？
这可以用二叉树来解释。 我想看下图就知道了。
这是递归图解，根节点首次进入move函数，第一个参数3按下大于1，第二个参数指向移动盘的原始位置，第四个参数指向移动目的地位置，第三个参数中继这幅图是按照程序画的。 上面的节点数是调用move函数的次数。 现在，让我们按中顺序遍历这个二叉树。
假设： a、b、c三个磁盘首先全部放置在one上，从a到c依次变大，表示c位于底部，a位于顶部，-表示移动。
节点4:a - z
节点2:b - y
节点5:a - y
节点1:c - z
节点6:a - x
节点3:b - z
节点7:a - z
完成。
如果有四个磁盘呢？ 那也可以说是同样的道理。 此时，有15个节点。 也就是说移动15次。 那有n个磁盘吗？ 2的n次方减去1……