递归之美：数学,电脑科学与分形.docVIP

递归之美：数学，电脑科学与分形——转自/2007/05/24/recursive/想像一下，我刚才说了一句话，那句话是：“想像一下，我刚才说了一句话，那句话是：“想像一下，我刚才说了一句话，那句话是：……….””，如此下去，就好像站在两面平行摆设的镜子中间，镜子中的影像不断的重复。再举个例子，写完一封信想要匿名必威体育官网网址，就署名“知名不具”。回信的人写：“知知名不具具”。之后再回信的时候就变成：知知知名不具具具，加上括号可能比较清楚：(知(知(知名不具)具)具)。 递归就是类似这样子，不断的重复同样的东西，只不过每次重复的是比较小的东西了。大家应该对数学归纳法不陌生，在使用数学归纳法时，我们首先确定n=1的时候某件事情是成立，然后在证明n到n+1的过程是正确的，就可以从n=1的例子，一路推论出第n项是什么东西。就像是推骨牌一样，把第一张牌推倒了之后，剩下的骨牌自然就被前面的骨牌给推倒。 递归的概念则是相反的方向：我们想要解决一个大小为n的问题，我首先做的事情是把问题化简成大小为n-1的问题，但是解决的方法还是一样，只不过大小是n-1。如此继续化简，最后变成大小为n=1的基本问题，接着只要n=1的基本问题解决了，原来大小为n的问题也跟着解决了。 这又好像层层分工。假设每个人都会加法，然后今天我想求出1+2+…+n等于多少？其中一个办法就是递归，我先假设1+2+…+(n-1)已经有人算好，那么我只要再加上n，就可以得到答案了。然而1+2+…+(n-1)要怎么得到呢？我就请另外一位朋友帮我算。另外一位朋友接到这个问题以后，也用同样的方法，他把1+2+…+(n-2)的结果交给另外一位朋友算，然后把这个结果加上(n-1)，就变成我想要的1+2+… +(n-1)了。朋友的朋友也继续用类似的方法，直到最后一位朋友只需要回答1，接着倒数第二位朋友就把1加上2，传给倒数第三位朋友，倒数第三位朋友加上3，一直到我收到1+2+…+(n- 1)的结果，再加上n，就大功告成了。不过可能会觉得，如此简单的问题，为何还需要递归呢？其实递归也是比较适合一些问题来解，也就是那些“解决方式一样，但是可以化成大小比较小”的问题，除此之外还可以轻松解决基本问题(n=1的时候)。举例来说，有个古老的问题叫做河内塔(Hanoi Tower)，问题的定义引述如下(引用网站) 1883年，一位法国的数学家Edouard Lucas教授在欧洲的一份杂志上介绍了一个相当吸引人的难题──迷人的智力游戏。这个游戏名为河内塔(Tower of Hanoi)，它源自古印度神庙中的一段故事(也有一说是Lucas教授为增加此游戏之神秘色彩而捏造的)。传说在古老的印度，有一座神庙，据说它是宇宙的中心。在庙宇中放置了一块上面插有三根长木钉的木板，在其中的一根木钉上，从上至下被放置了64片直径由小至大的圆环形金属片。古印度教的天神指示祂的僧侣们将64片的金属片移至三根木钉中的其中一根上。规定在每次的移动中，只能搬移一片金属片，并且在过程中必须保持金属片由上至下是直径由小至大的次序，也就是说不论在那一根木钉上，圆环形的金属片都是直径较小的被放在上层。直到有一天，僧侣们能将64片的金属片依规则从指定的木钉上全部移动至另一根木钉上，那么，世界末日即随之来到，世间的一切终将被毁灭，万物都将至极乐世界。 倘若这个故事的叙述为真，那么，我们只需加速移动金属片，是不是就能愈早到达极乐世界呢？果真要移动这64片金属片，那么，至少要花几次的搬动才能完成呢？有没有规律可循呢？ 这个问题，就很符合刚才的特性：我们可以把大问题化成小问题，而且解决的方法相同，只不过问题的大小变小了。另外基本问题(n=1)，就是移动一根金属片所需要的次数，这个我们也可以轻易解决，所以这个问题就可以用递归来解。 首先，我们假设有A、B、C三根柱子，这64片金属片一开始在柱子A上面，我们想要搬到柱子C。因为问题中规定某个金属片上面是空的时候才能移动，我们就假设有个人可以帮我们把63片比较小的金属片先从柱子A搬到柱子B上面，然后我们把最大的那一片从柱子A搬到柱子C，再请那位朋友把刚才的63片从柱子B搬到柱子C，整个问题就解决了。然后我们只要知道刚才那位朋友搬了几次，然后加上我们自己般动的1次，就是整个问题要求的搬动次数了。 递归不仅仅在数学上有其重要性，在电脑科学之中扮演的角色更是至关重要。程式设计者对于递归绝对不会陌生，上面所举的河内塔问题，实际上也是电脑科学的经典例子之一，是初学程序设计的人一定会学到的东西。递归的思维，常常可以让程式设计者打造出简洁的程式，让繁冗的问题透过简单的程式码来解决(例如parser的设计)。演算法上所讲的dynamic programming，就是递归思维在演算法的具体呈现。