Recursion递归

lst = range(101)
def s(a):
    if len(a) == 1:
        return a[0]
    return a[0]+s(a[1:])
print(s(lst))　　#5050

思路：用首项和余项相加。

实现：两个关键处，第一，三行这是递归结束的条件；第二，五行调用函数自己，实现递归

递归三定律：

递归算法必须有结束条件
递归算法必须改变自己的状态（数据量趋小），并向结束条件演进
递归算法必须递归地调用自己

例1：任意十进制数转化为相应的字符串形式。

def convert(n):
    i,j = divmod(n,10)
    if j<10 :
        return str(i)+str(j)
    return convert(i)+str(j)

print(repr(convert(998)))　　#'998'

大于一位的数字不能直接转换，要先将给定数字拆成单位，因为余数为单位，故基本条件设为原数字中最大位的数字化为单位。

递归过程要向把所有非单位数字都转化为单位演进，即满足基本条件

调用自己时，参数为需要转化的除数 i

例2：十进制转为2进制

def convert(n):
    i,j = divmod(n,2)
    if i < 2 :
        return str(i)+str(j)
    return convert(i)+str(j)

print(repr(convert(25)))　　#'11001'

通用方法，栈帧递归：

from linear import Stack　　#导入之前的stack类

s = Stack()

def toStr(n,base):
    convertString = "0123456789ABCDEF"
    while n > 0:
        if n < base:
            s.push(convertString[n])
        else:
            s.push(convertString[n % base])
        n = n // base
    res = ""
    while not s.isEmpty():
        res = res + str(s.pop())
    return res

print(toStr(25,2))

可视递归：

螺旋线：

import turtle

myTurtle = turtle.Turtle()　　#海龟作图
myWin = turtle.Screen()　　#作图窗口

def drawSpiral(myTurtle,lineLen):
    if lineLen > 0:
        myTurtle.forward(lineLen)　　#前进步数
        myTurtle.right(90)　　　　　　#右转：角度，这里是右转90度
        drawSpiral(myTurtle,lineLen-5)

drawSpiral(myTurtle,100)
myWin.exitonclick()　　#单击退出作图窗口

分形树：

import turtle

def tree(branckLen,t):
    if branckLen > 5:
        t.forward(branckLen)
        t.right(20)
        tree(branckLen-15,t)
        t.left(40)
        tree(branckLen-15,t)
        t.right(20)
        t.backward(branckLen)

def main():
    t = turtle.Turtle()
    myWin = turtle.Screen()
    t.left(90)　　#起始方向向右，左转后向上
    t.up()　　　　#将尾巴抬起，移动不留痕迹
    t.backward(100)　　#后退100，让图更处于画屏中央
    t.down()　　#尾巴放下，移动留下痕迹
    t.color("green")　　#图标颜色
    tree(75,t)
    myWin.exitonclick()

main()

谢尔宾斯基三角形：

在一个三角形中取各边中点并连接，就把原来三角形分成四个，然后忽略中间的三角形对其它三角形再重复以上步骤。。。用到三向递归算法

理论上可以无限分割，但使用递归得到它时要找到结束条件，结束条件就是分割的次数，该值被称为相似性维数，每当执行一次递归调用，相似性维数就减去1，直到0为止。

实现：（再探究）

import turtle

def drawTriangle(points,color,myTurtle):
    myTurtle.fillcolor(color)
    myTurtle.up()
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.down()
    myTurtle.begin_fill()
    myTurtle.goto(points[1][0],points[1][1])
    myTurtle.goto(points[2][0],points[2][1])
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.end_fill()

def getMid(p1,p2):
    return ( (p1[0]+p2[0]) / 2,(p1[1] + p2[1]) / 2)

def sierpinski(points,degree,myTurtle):
    colormap = ['blue','red','green','white','yellow',
                'violet','orange']
    drawTriangle(points,colormap[degree],myTurtle)
    if degree > 0:
        sierpinski([points[0],
            getMid(points[0],points[1]),
            getMid(points[0],points[2])],
            degree-1,myTurtle)
        sierpinski([points[1],
            getMid(points[0],points[1]),
            getMid(points[1],points[2])],
            degree-1,myTurtle)
        sierpinski([points[2],
            getMid(points[2],points[1]),
            getMid(points[0],points[2])],
            degree-1,myTurtle)

def main():
    myTurtle = turtle.Turtle()
    myWin = turtle.Screen()
    myPoints = [[-100,-50],[0,100],[100,-50]]
    sierpinski(myPoints,3,myTurtle)
    myWin.exitonclick()

main()

View Code

河内塔：

def moveTower(height,fromPole,toPole,withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)

def moveDisk(fp,tp):
    print('moving disk from',fp,'to',tp)

moveTower(3,'A','B','C')

渐变 --> 突变