递归

来自计算思维百科
跳转至: 导航搜索
递归1.png

美国影片“盗梦空间”是一部关于现实与梦境交相辉映的电影。电影讲述的是主人公诺兰进入希里安·墨菲梦境植入想法的行动。为了向希里安·墨菲梦植入理念,影片进入四层梦境,即所谓:“梦中的梦中 梦中人的梦中”。

《盗梦空间》从现实进入第一层梦,从第一层梦进入第二层,直到第四层。然后再从第四层返回第三层,从第三层返回第二层,故事其实是一个递归的过程。

基本概念

递归(Recursive)是直接或间接地调用自身的算法。它的另一种定义是,用自己的简单情况,定义自己。

欧几里德算法就是递归算法。m、n的最大公约数等于n、m mod n的最大公约数,用自己的小数据定义自己。

应用

在很多数学趣味问题中,递归是非常常见的一种方法,而在实际生活和工作中也有大量应用。

德罗斯特效应

德罗斯特效应('Droste Effect')是递归的一种视觉形式,是指一张图片的某个部分与整张图片相同,如此产生无限循环。图1是德罗斯特效应的一个例子。

德罗斯特效应的名称源于荷兰著名厂牌德罗斯特可可粉的包装盒,包装盒上的图案是一位护士拿着一个有杯子及纸盒的托盘,而杯子及纸盒上的图案和整张图片相同。这张图片从1904年起开始使用,数十年间只进行了一些小幅的调整,后来成为一个家喻户晓的概念。诗人及专栏作家Nico Scheepmaker在七十年代起,开始使用“德罗斯特效应”一词。

如果你想体会德罗斯特效应,可以拿两面镜子,相对平行摆放,然后站在两面镜子中间,在镜子里会看到相同的、无限循环的场景。德罗斯特效应图片是网友通过名为Mathmap的数学软件制作出来的。

9.2.2.png


算法中的递归不同于德罗斯特效应。后者照片里的情景好像是无限循环的,但前者必须有终止计算的时刻。大数据用小数据定义,小数据用更小的数据定义,如此下去,若无终止计算的时刻,则形成了死循环,与算法的有穷性特征不符。

Fibonacci数列

1202年,意大利数学家斐波那契出版了他的《算盘全书》。他在书中提出了一个关于兔子繁殖的问题:如果一对兔子每月能生一对小兔(一雄一雌),而每对小兔在他出生后的第三个月里,又能开始生一对小兔,假定在不发生死亡的情况下,由一对出生的小兔开始,50月后会有多少对兔子?

显然,第一个月只有一对兔子,第二个月仍只有一对兔子,第三个月兔子对数为第二个月兔子对数加第一月兔子新生的对数。同理,第i个月兔子对数为第i-1月兔子对数加第i-2月兔子新生的对数。即从第一个月开始计算,每月兔子对数依次为: 1,1,2,3,5,8,13,21,34,55,89,144,233…,此数列称为Fibonacci'数列('Fibonacci'Sequence'),也称兔子数列。

根据上述分析,可按如下公式递归地定义Fibonacci数列(Fi):

Fibonacci数列递归实现的伪代码如下:     9.2.3.png

输入:正整数n

输出:Fibonacci数列的第n项

Fib(n)                              

1  IF n≤2

2 THEN RETURN 1                      

3  RETURN Fib(n-1)+Fib(n-2)    //调用自身                       

Fibonacci数列也称黄金分割数列,因为其相邻两项的比值越来越趋近黄金分割比例0.6180339887…。Fibonacci数列在现代物理、化学、经济等领域都有直接应用。它与自然界的许多现象也有很多巧合,如与植物花瓣、叶、径等,许多植物的花瓣、叶等呈现着Fibonacci数列特性。斐波那契以兔子问题猜中了大自然的奥秘。

                         9.2.4.png


                                        图1  Fib(5)的调用图

通过图1可以理解Fibonacci数列对自身的调用。图1给出了n=5时,Fib(5)的计算过程。从图中可以看出,为计算Fib(5),需计算Fib(4)、Fib(3),为计算Fib(4),需计算Fib(3)和Fib(2),依次调用下去,直到Fib(1)或Fib(0)。

图1中有些值被重复计算多次,如Fib(2)、Fib(3)、Fib(1)、Fib(0)。当n更大时,这种重复计算越来越严重,因此,Fibonacci数列递归算法的效率很低。

盗梦空间

美国影片《盗梦空间》是一部关于现实与梦境交相辉映的电影。电影讲述的是主人公诺兰进入希里安.墨菲梦境植入想法的行动。影片中,诺兰依次展开的六层空间叙事,分别是现实世界、第一层梦境(城市)、第二层梦境(酒店)、第三层梦境(雪域)、第四层梦境(高楼)以及潜意识边缘(limbo),其中每层梦境经历的时间是前一层的20倍。影片中不断出现的时空跨度以及梦境与现实、梦境与梦境之间的交互转换,确实让人有种“脑细胞死一地”的感觉。 解决:用计算机思维来解释,《盗梦空间》的故事其实是一个递归的过程,它使用的是梦的“递归”结构模式,将六层空间嵌套起来。

求N!

案例: 有一对兔子,每隔一个月会产下一对小兔子,小免子每隔一个月,也会产生新的一对免子,问12个月后,共有多少对兔子。 我们要设计一个函数g(n)求解第n个月的兔子个数,那么第n个月的兔子个数是第n-1个月兔子个数的两倍,就是g(n)=g(n-1)*2,可以看到,在利用g(n)自己求解自己时,问题规模减小了,同时,我们知道g(1)=2,就是最小规模的问题的解可以知道,那这个递归函数就可以得到了。

评价

虽然,递归对某些问题而言存在重复调用,导致算法效率不高,但对一些特别的问题,如汉诺塔,用递归实现比非递归实现简单、易于理解。

可以体现的计算思维

递归能够将一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,只需少量步骤就可描述出解决问题过程所需要的多次重复工作,大大地减少了工作量。这样做的目的是把一个大型复杂的问题层层转化,最终成为一个与原问题相似但规模小很多的问题来以便于求解。