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 resprint(toStr(25,2))
可视递归：
螺旋线：
import turtlemyTurtle = 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 turtledef 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 turtledef 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()
河内塔：
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')