一.函数递归
1.什么是递归调用
- 递归调用是函数嵌套调用的一种特殊形式
- 函数在调用时, 直接或间接调用了本身, 这就是递归调用
- 递归的本质就是循环
2.直接和间接调用本身示例
- 直接调用 : 死循环, 无意义
def f1():
print('from f1')
f1()
f1() # 当超过递归最大深度时报错 "RecursionError"
- 间接调用
def bar():
print('sa')
foo()
def foo():
print('sds')
bar()
foo() # 这样来回调用无意义, 当超过递归最大深度时报错 "RecursionError"
3.设置递归最大深度
- 调用函数会产生局部的名称空间，占用内存，因为上述这种调用会无休止调用本身
- 为了防止其无限制占用内存，python 解释器的内存管理机制对函数的递归调用做了最大的层级限制
ps : 虽然可以修改, 但应该有边界, 不可能无限制的递归, 那样无意义, 递归应分为明确的两个阶段 (回溯, 递推)
import sys
print(sys.getrecursionlimit()) # 默认1000
sys.setrecursionlimit(2000) # 可以改
print(sys.getrecursionlimit()) # 2000
4.递归的两个阶段
-
回溯
回溯就是从外向里层一层一层递归调用下去
回溯阶段必须要有一个明确的结束条件
每次进入下一次递归时, 问题的规模应该减少,否则单纯的无限的递归毫无意义
-
递推
递推就是从里到外一层一层结束递归
- 示例
"回溯阶段"
age(5)=age(4)+2
age(4)=age(3)+2
age(3)=age(2)+2
age(2)=age(1)+2
age(1)=18 # 求 age(5) 的值
先研究表达式如何成立
n > 1 : age(n) = age(n-1) + 2
n = 1 : age(n) = 18
写函数计算 : "递推阶段"
def age(n):
if n == 1:
return 18
return age(n-1)+2 # age(4)+2 = age(3)+2+2 = age(2)+2+2+2 = age(1)+2+2+2+2 = 18+8 = 26
print(age(5)) # 26
5.总结
- 递归一定要有一个明确的结束条件(必须在满足某种条件下结束)
- 每次进入下一次递归, 问题的规模都应该减少
- 在 Python 中没有尾递归优化
什么是问题规模减少简单示例:
将不是列表的值打印出来
l = [1, [2, [3, [4, [5, [6, [7, [8, [9]]]]]]]]]
def outter(itmes):
for line in itmes:
if type(line) is not list:
print(line)
else:
outter(line)
outter(l) # 1,2,3,4,5,6,7,8,9
二. 二分法
1.什么是算法
- 算法是高效解决问题的方法
- 二分法就是一种算法
2.二分法示例
- 想要从一个从小到大排列的成千上万个值中找到指定的值
- 如果使用遍历的话效率太低
- 那么二分法就可以极大的缩小问题的规模, 以次来提高效率
nums = [-23,-2,4,5,8,90,234,345,467,786,978,8900] # 从小到大排列
def check(num,l):
print(l)
if len(l) == 0:
print("不存在这个值")
return
mid_num = len(l) // 2
if num > l[mid_num]: # 说明在中间值得右边
l = l[mid_num+1:] # 使用切片将右边的值从新赋值给 l
check(num,l) # 递归
elif num < l[mid_num]: # 说明在中间值得右边
l = l[:mid_num] # 使用切片将右边的值从新赋值给 l
check(num,l) # 递归
else:
print("OK!")
check(8900,nums) # OK!