递归是一种解决问题的方法，将问题分解为更小的子问题，直到得到一个足够小的问题可以被很简单的解决，通常递归涉及函数调用自身。

递归实现整数列表求和

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. 递归算法必须改变其状态并向基本情况靠近。
3. 递归算法必须以递归方式调用自身。
   首先，基本情况是算法停止递归的条件。基本情况通常是足够小以直接求解的问题。在listsum算法中，基本情况是长度为 1 的列表。
   为了遵守第二定律，我们必须将算法向基本情况的状态改变。状态的改变意味着该算法正在使用的一些数据被修改。通常，表示问题的数据在某种程度上变小。在listsum算法中，我们的主要数据结构是一个列表，因此我们必须将我们的状态转换工作集中在列表上。因为基本情况是长度 1 的列表，所以朝向基本情况的自然进展是缩短列表。
   最后的法则是算法必须调用自身。这是递归的定义。

递归的应用

整数转换为任意进制字符串

例如将769转换成十进制的字符串的过程可以表示为：

整数转换为任意进制字符串

def toStr(n,base):
    convertString = "0123456789ABCDEF"
    if n < base:
        return convertString[n]
    else:
        return toStr(n // base,base) + convertString[n % base]

print(toStr(10,2))

计算过程可以表示为：

整数转换为任意进制字符串

递归可视化

示例1

import turtle

myTurtle = turtle.Turtle()
mywin = turtle.Screen()

def drawSpiral(myTurtle,lineLen):
    if lineLen > 0:
        myTurtle.forward(lineLen)
        myTurtle.right(90)
        drawSpiral(myTurtle,lineLen-5)

drawSpiral(myTurtle,100)
turtle.done()

递归绘图1

示例2

将绘制一个分形树。分形来自数学的一个分支，并且与递归有很多共同之处。分形的定义是，当你看着它时，无论你放大多少，分形有相同的基本形状。

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

def main():
    t = turtle.Turtle()
    myWin = turtle.Screen()
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("green")
    tree(75,t)
    turtle.done()

main()

效果：

递归实现分形树