末日的100条预言（一个世界末日传说）
末日的100条预言（一个世界末日传说）图演示如下：如果有五个圆盘，那就要31步，过程如下图。2．设金片只有二片。可先将较小金片移至乙针上，较大金片移至丙针上，再将较小金片从乙针移至丙针上，共移动3次。3．设金片有三片。可先将上面两片金片移到乙上。按2可知，共需移动3次。再把第三片移至丙，又移一次。下面把乙上两片移至丙同2，还需三次。以上共需2·3 1=7（次）。动图演示如下：4．设金片有四片。先把上面三片移至乙，按3需7次。再把第四片从甲移到丙上，又移一次。最后，把较小的三片从乙移至丙，又需移7次。以上共需移动2·7 1=15（次）。图演示如下：
在印度北部的一个佛教的圣庙里，桌上的黄铜板上，放着三根宝石针，每根长约0.5米。据说印度教的主神梵天在创造世界时，在其中的一根针上，自上而下由大到小放了六十四片金片。每天二十四小时内，都有僧侣值班，按照以下的规律，不停地把这些金片在三根宝石针上移来移去：每次只准移动一片，且不论在那根针上，较小的金片只能放在较大的金片上。当所有六十四片金片都从梵天创造世界时所放的那根针上移到另一根针上时，世界的末日就要到临。
这虽是一个传说，但却引起人们的重视，大家都想知道僧侣移动完毕这六十四片金片需要多少时间。也就是说，人类在这个世界上还可以生存多少时间。让我们来算算看。
设原来放置金片的宝石针为甲，其它两根针为乙、丙。
1．设金片只有一片。显然，只要移动1次即可。
2．设金片只有二片。可先将较小金片移至乙针上，较大金片移至丙针上，再将较小金片从乙针移至丙针上，共移动3次。
3．设金片有三片。可先将上面两片金片移到乙上。按2可知，共需移动3次。再把第三片移至丙，又移一次。下面把乙上两片移至丙同2，还需三次。以上共需2·3 1=7（次）。动图演示如下：
4．设金片有四片。先把上面三片移至乙，按3需7次。再把第四片从甲移到丙上，又移一次。最后，把较小的三片从乙移至丙，又需移7次。以上共需移动2·7 1=15（次）。图演示如下：
如果有五个圆盘，那就要31步，过程如下图。
图演示如下：
试试找找圆盘数和移动次数之间的关系和规律吧！
利用构造函数也可以确定这个问题，设 f ( n ) 为有 n 个圆盘时的最少移动次数，那么必然有 f ( n ) = 2 f ( n - 1 ) 1 。即先将 n-1 个圆盘从初始的 A 柱移到 B 柱，再将最大的第 n 个圆盘从 A 柱移到 C 柱，最后将 B 柱上所有的 n-1 个圆盘移到 C 柱上。
但是，为了计算出 f ( n )，我们还需要求出 f ( 1 ) ~ f ( n-1 )，未免有些麻烦和多余，那么可不可以找出一个比较简单的通项公式呢？当时，我们只不过使用了枚举前面的几个 f ( n ) 而推断出 f ( n ) = 2 ^ n -1，却并未给出一个很好的证明，今天就来讲一讲吧。由于输入法的不方便，每一段后面都有相应的图片解释，文末有所有的推导过程。
如果光靠 f，恐怕是无法求出这样的结果的，现在，我们就有请母函数登场！在借助母函数后，我们就可以较容易地得到答案了。设 g ( x )是 f 的母函数，g ( x ) = f ( 0 ) f ( 1 ) x f ( 2 ) ( x ^ 2 ) f ( 3 ) ( x ^ 3 ) …… f ( i ) ( x ^ i ) ……（这样无穷地加下去）同时，不要忘记 f ( n ) - 2 f ( n - 1 ) = 1，并想办法利用好这一特点。用类似无穷等比数列求和的方式，将等式两边同时乘以 2x（至于理由，等会儿你就知道了），得到：2x g ( x ) = 2x f ( 0 ) 2 f ( 1 ) ( x ^ 2 ) 2 f ( 2 ) ( x ^ 3 ) 2 f ( 3 ) ( x ^ 4 ) ……。
把第一个式子（完美地）减去第二个式子（第一个式子中的第一项 f ( 0 ) 为 0，直接舍去，其余都保留，并合并 x，x ^ 2，x ^ 3 ……）：( 1 - 2x ) g ( x ) = x ( f ( 1 ) - 2 f ( 0 ) ) ( x ^ 2 ) ( f ( 2 ) - 2 f ( 1 ) ) ( x ^ 3 ) ( f ( 3 ) - 2 f ( 2 ) ) ……此时，你就会发现，f ( 1 ) - 2 f ( 0 ) = f ( 2 ) - 2 f ( 1 ) = f ( 3 ) - 2 f ( 2 ) = …… = 1！为了利用好 f ( n ) - 2 f ( n - 1 ) = 1，这也就解释了为什么之前需要等式两边同时乘以 2x。
所以说，( 1 - 2x ) g ( x ) = x x ^ 2 x ^ 3 …… = x ( 1 x x ^ 2 …… ) = x / ( 1- x )，g ( x ) = x / ( ( 1-x ) × ( 1 - 2x ) )。当然，这种形式并不令我们感到满足，毕竟分母是一个乘法多项式。所以，我们可以进一步（用类似因式分解的做法或设系数皆可）得到： g ( x ) = 1 / ( 1 - 2x ) - 1 / ( 1- x )。同时，我们有：1 / ( 1 - 2x ) = 1 2x (2x)^ 2 (2x) ^ 3 ……，1 / ( 1-x ) = 1 x x ^ 2 x ^ 3 ……。将它们合并后再合并同类项，得到：g ( x ) = ( 2 - 1) x ( 2 ^ 2 - 1) ( x ^ 2 ) ( 2 ^ 3 - 1 ) ( x ^ 3 )……，
而由于对应系数相等，即 f ( 1 ) = 2 - 1，f ( 2 ) = 2 ^ 2 - 1，f ( 3 ) = 2 ^ 3 - 1……我们就可以推出：f ( n ) = 2 ^ n - 1，得证！这样可以大大减少我们的计算量，并且适当地提高效率。其实，利用这个 " 似函数，非函数 " 的辅助工具—— " 函数的妈妈 "，母函数，我们就可以解决很多关于求出函数通项公式的问题。而斐波那契数列的通项公式，再也不需要去枚举了（何况你也很难枚举出规律），我们就可以直接用母函数来解决啦！
要完成移动一个n层的汉诺塔需要多少步呢？光靠枚举，就可以推断是：
按照现代的宇宙进化论，恒星、太阳、行星（包括地球）是在三十亿年前由不定形物质形成的。我们还知道，给恒星特别是给太阳提供能量的"原子燃料"还能维持100～150亿年。因此，我们太阳系的整个寿命无疑要短于二百亿年。可见远不等僧侣们完成任务，地球早已毁灭了。
这个传说就是经典的汉诺塔问题，不仅是一个著名的数学问题，也是一款好玩、益智的游戏。对于N个圆盘，可以先将上面N-1个圆盘看成一个整体，假想已经移动到中间柱，然后把第N个盘移动到目标柱。接着再把N-1个圆盘看成N'，按照上面的进行迭代，一步一步地倒推出第一个圆盘应当如何移动，所用的即是递归的思想。
在高中数学中，递归思想常常见于数列中递推公式的应用。此外，递归法作为一种解决问题的思维方式，在计算机编程中应用十分广泛。从算法的角度看，递归思想即是程序调用自身的编程技巧，利用算法知识，将大问题化成同样形式、但是规模更小的小问题，最后用计算机的计算能力，将更简单的初始情况反推回任何规模的问题答案。
