递归(Recursion)及其应用

1. 什么是递归

递归是一种解决问题的方法，其精髓在于将问题分解为规模更小的相同问题，持续分解，直到问题规模小到可以用非常简单直接的方式来解决。 递归问题分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。

2. 递归的应用

2.1 数列求和

数列求和[1,3,5,7,9] 换个方式来表达数列求和：全括号表达式（1+（3+（5+（7+（9））））） 上面这个式子，最内层的括号（7+9）是无需循环即可计算的，实际上整个求和过程如下： 观察上述过程中所包含的重复模式，可以把求和问题归纳成这样： 数列的和=“首个数”+“余下数列” 如果数列包含的数烧到只有1个的话，它的和就是这个数。

上述递归算法的python实现

def listsum(numList): if len(numList)==1: return numList[0] else: return numList[0]+listsum(numList[1:]) print(listsum([1,3,5,7,9]))

上面程序的要点： 1.问题分解为更小规模的相同问题，表现为“调用自身” 2.对最小规模问题的解决：简单直接 递归函数调用和返回过程的链条如下图所示

递归“三定律”

为了向阿西莫夫的“机器人三定律”致敬，递归算法也总结出“三定律” 1.递归算法必须有一个基本结束条件（最小规模问题的直接解决） 2.递归算法必须能改变状态向基本结束条件演进（减小问题规模） 3.递归算法必须调用自身（解决减小了规模的相同问题） 数列求和问题中的递归“三定律” 1.数列求和问题首先具备了基本结束条件：当列表长度为1的时候，直接输出所包含的唯一数 2.数列求和处理的数据对象是一个列表，而基本结束条件是长度为1的列表，那递归算法就要改变列表并向长度为1的状态演进 3.调用自身。更短数列的求和问题。

2.2 整数转换为任意进制

余数总小于“进制基base”是“基本结束条件”，可直接进行查表转换 整数商成为“更小规模”问题，通过递归调用自身解决。 ####python代码实现

#整数转任意进制 def toStr(n,base): convertString="0123456789ABCDEF" if n <base: return convertString[n] else: return toStr(n//base,base)+convertString[n%base] print(toStr(34,2))

2.3 汉诺塔

汉诺塔问题是法国数学家Edouard Lucas于1883年根据传说提出来的。 传说在一个印度教寺庙里，有3根柱子，其中一根套着64个由小到大的黄金盘片，僧侣们的任务就是要把这一叠黄金盘片从一个柱子搬到另一根，但有两个规则： 1.一次只能搬一个盘子； 2.大盘子不能叠在小盘子上

汉诺塔问题：递归思路

将盘片塔从开始柱，经由中间柱，移动到目标柱： 首先将上层N-1个盘片的盘片塔从开始柱经由目标柱移动到中间柱 然后将第N个（最大的）盘片从开始柱移动到目标柱 最后将放置在中间柱的N-1个盘片的盘片塔经由开始柱移动到目标柱 基本结束条件，即最小规模问题是：1个盘片的移动问题

python代码实现

#汉诺塔问题 def moveTower(height,frompole,withpole,topole): if height>=1: moveTower(height-1,frompole,topole,withpole) moveDisk(height,frompole,topole) moveTower(height-1,withpole,frompole,topole) def moveDisk(disk,frompole,topole): print(f"Moving disk[{disk}] from {frompole} to {topole}") moveTower(3,"#1","#2","#3")

2.4 找零兑换

假设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量的硬币。 首先是确定基本结束条件，兑换硬币找给问题最简单直接的情况就是，需要兑换的找零其面值正好等于某种硬币。如找零25分，答案就是1个硬币！ 其次是减小问题规模，对每种硬币尝试一次，例如美元硬币体系： 找零减去1分(penny)后，求兑换硬币最少数量（递归调用自身）； 找零减去5分(nikel)后，求兑换硬币最少数量 找零减去10分(dime)后，求兑换硬币最少数量 找零减去25分(quarter)后，求兑换硬币最少数量。 上述四项中选择最小的一个。

python代码实现

#找零问题 import time def recMC(coinValueList,change): minCoins =change if change in coinValueList: return 1#最小规模直接返回 else: for i in [c for c in coinValueList if c< change]: numCoins=1+recMC(coinValueList,change-i)#调用自身，减小规模：每次减去一种硬币面值，挑选最小数量 if numCoins<minCoins: minCoins=numCoins return minCoins print(time.clock()) print(recMC([1,5,10,25],63)) print(time.clock())

递归解法虽然能解决问题，但其最大的问题是非常低效。 对63分的兑换硬币问题，需要进行67,716,925次递归调用！在我的笔记本电脑上花费了近50秒的时间得到解：6个硬币。 对这个递归解法ji9nxing改进的关键在于消除重复计算，我们可以用一个表将计算过的中间结果保存起来，在计算之前查表看看是否已经计算过。 这个算法的中间结果就是部分找零的最优解，在递归调用过程中已经得到的最优解被记录下来。在递归调用之前，先查找表中是否已有部分找零的最优解。如果有，直接返回最优解而不进行递归调用；如果没有，才进行递归调用。

python代码实现

#找零问题改进算法 import time def recDC(coinValueList,change,knowResults): minCoins=change if change in coinValueList:#递归基本结束条件 knowResults[change]=1#记录最优解 return 1 elif knowResults[change]>0: return knowResults[change]#查表成功，直接用最优解 else: for i in [c for c in coinValueList if c< change]: numCoins=1+recDC(coinValueList,change-i,knowResults) if numCoins<minCoins: minCoins=numCoins #找到最优解记录到表中 knowResults[change]=minCoins return minCoins memo=[0]*64 print(time.clock()) print(recDC([1,5,10,25],63,memo)) print(time.clock()) print(memo)

改进后的解法，极大地减少了递归调用次数，对63分兑换硬币问题，仅需要221次递归调用，是改进前的三十万分之一，瞬间返回！

3.递归可视化：图示

3.1 python的海归作图系统turtle module

python内置，随时可用，以LOGO语言的创意为基础，其意象为模拟海龟在沙滩爬行而留下的足迹。 爬行：forward(n);backward(n) 转向：left(a);right(a) 抬笔放笔：penup();pendown() 笔属性：pensize(s);pencolor©

3.1.1 长度为100的直线

import turtle t=turtle.Turtle() #开始作图 t.forward(100)#指挥海龟作图 #作图结束 turtle.done()

3.1.2 正方形

#画一个正方形 import turtle t=turtle.Turtle() #开始作图 for i in range(4): t.forward(100) t.right(90) turtle.done()

3.1.3 五角星

#画一个五角星 import turtle t=turtle.Turtle() t.pencolor('red') t.pensize(3) #开始作图 for i in range(5): t.forward(100) t.right(144) t.hideturtle() turtle.done()

3.1.4 螺旋

#螺旋 import turtle t=turtle.Turtle() def drawSpiral(t,linelen): if linelen>0:#最小规模，0直接退出 t.forward(linelen) t.right(90) drawSpiral(t,linelen-5)#调用自身，减小规模，边长减小5 drawSpiral(t,100) turtle.done()

3.2 分形数：自相似递归图形

分形Fractal，是1975年由Mandelbrot开创的新学科。“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。 分形是在不同尺度上都具有相似性的事物，我们能看出一棵树的每个分叉和每条树枝，实际上都具有整棵树的外形特征（也是逐步分叉的）。这样，我们可以把树分解为三个部分：树干、左边的小树、右边的小树。分解后，正好符合诋毁的定义：对自身的调用

python代码实现

import turtle t=turtle.Turtle() t.pencolor('green') t.pensize(3) def tree(branch_len): if branch_len>5:#树干太短不画，即递归结束条件 t.forward(branch_len) t.right(20)#右倾斜20度 tree(branch_len-10)#递归调用，画右边的小树，树干减10 t.left(40)#向左回40度，即左倾斜20度 tree(branch_len-10)#递归调用，画左边的小树，树干减10 t.right(20)#向右回20度，即回正 t.backward(branch_len)#海归退回原位置 t.left(90) t.penup() t.backward(100) t.pendown() tree(75)#画树干长度为75的二叉树 t.hideturtle() turtle.done()

3.3 递归可视化：谢尔宾斯基三角形

根据自相似特性，谢尔宾斯基三角形是由3个尺寸减半的谢尔宾斯基三角形按照品字形拼叠而成。由于我们无法真正作出谢尔宾斯基三角形（degree趋于无穷），只能做degree有限的近似图形。 在degree有限的情况下，degree=n的三角形是由3个degree=n-1的三角形按照品字形拼叠而成。同时，这3个degree=n-1的三角形边长均为degree=n的三角形的一半（规模减小）。当degree=0,则就是一个等边三角形，这是递归基本结束条件。

python代码实现

#递归可视化：谢尔宾斯基三角形 import turtle def sierpinski(degree,points): colormap=['blue','red','green','white','yellow','orange'] drawTriangle(points,colormap[degree])#画等边三角形 if degree>0:#最小规模，0直接退出 #减小规模，getMid边长减半，调用自身，左上右次序 sierpinski(degree-1,{'left':points['left'],'top':getMid(points['left'],points['top']),'right':getMid(points['left'],points['right'])}) sierpinski(degree-1,{'left':getMid(points['left'],points['top']),'top':points['top'],'right':getMid(points['top'],points['right'])}) sierpinski(degree-1,{'left':getMid(points['left'],points['right']),'top':getMid(points['top'],points['right']),'right':points['right']}) #绘制等边三角形 def drawTriangle(points,color): t.fillcolor(color) t.penup() t.goto(points['top']) t.pendown() t.begin_fill() t.goto(points['left']) t.goto(points['right']) t.goto(points['top']) #取两个点的中点 def getMid(p1,p2): return ((p1[0]+p2[0])/2,(p1[1]+p2[1])/2) t=turtle.Turtle() t.pensize(2) points={'left':(-200,-100),'top':(0,200),'right':(200,-100)} #画degree=5的三角形 sierpinski(5,points) turtle.done()