[数据结构与算法]Python数据结构与算法(4)--递归

递归

1.初始递归

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

# 数列的和=“ 首个数” +“ 余下数列” 的和
# 如果数列包含的数少到只有1个的话，它的和就是这个数了
def listsum(numList):
    if len(numList) == 1:
        return  numList[0]
    else:
        return numList[0] + listsum(numList[1:])

• 递归“三定律”

1，递归算法必须有一个基本结束条件（最小规模问题的直接解决）
2，递归算法必须能改变状态向基本结束条件演进（减小问题规模）
3，递归算法必须调用自身（解决减小了规模的相同问题）

2.递归的应用

1.数列求和

# 数列的和=“ 首个数” +“ 余下数列” 的和
def listsum(numList):
    if len(numList) == 1:
        return  numList[0]# 最小规模
    else:
        return numList[0] + listsum(numList[1:]) 
        #调用自身减小规模

2.任意进制转换

def toStr(n,base):
    convertString = "0123456789ABCDEF"
    if n<base:
        return convertString[n] # 最小规模
    else:
        return toStr(n//base,base) + convertString[n%base]
        #调用自身减小规模

3.递归调用的实现

• 当一个函数被调用的时候，系统会把调用时的现场数据压入到系统调用栈
  ? 每次调用，压入栈的现场数据称为栈帧
  ? 当函数返回时，要从调用栈的栈顶取得返回地址
  ? 恢复现场，弹出栈帧，按地址返回
  

• 在调试递归算法程序的时候经常会碰到这样的错误：RecursionError(超过递归深度限制)
  递归的层数太多，系统调用栈容量有限
  这时候要检查程序中是否忘记设置基本结束条件，导致无限递归
  或者向基本结束条件演进太慢，导致递归层数太多，调用栈溢出

• 在Python内置的sys模块可以获取和调整最大递归深度

print(sys.getrecursionlimit())
sys.setrecursionlimit(3000)
print(sys.getrecursionlimit())

# 结果：
# 1000
# 3000

• recursion：递归

4. 递归可视化 分形树

• Python的海龟作图系统turtle module基础
• 其意象为模拟海龟在沙滩上爬行而留下的足迹

爬行： forward(n); backward(n)
转向： left(a); right(a)
抬笔放笔： penup(); pendown()
笔属性： pensize(s); pencolor(c)

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()

• 分形树：自相似递归图形:
  一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状” ，即具有自相似的性质。
  自然界中能找到众多具有分形性质的物体海岸线、山脉、闪电、云朵、雪花、树等

# 树分解为三个部分：树干、左边的小树、右边的小树
# 分解后，正好符合递归的定义： 对自身的调用
import turtle

def tree(branch_len):
    if branch_len > 5: #树干太短不画，即递归结束条件
        t.forward(branch_len)#画树干
        t.right(20) #右倾鞋20度
        tree(branch_len - 15)#递归调用，画右边的小树，树干减15
        t.left(40) #向左回40度，即左倾斜20度
        tree(branch_len - 15)#递归调用，画左边的小树，树干减15
        t.right(20) # 向右回20度，即回正
        t.backward(branch_len) #海龟退回原位置

t = turtle.Turtle()
t.left(90)
t.penup()
t.backward(100)
t.pendown()
t.pencolor('green')
t.pensize(2)
tree(75)
t.hideturtle()
turtle.done()