35 函数递归与二分法

483次阅读

共计 1525 个字符，预计需要花费 4 分钟才能阅读完成。

递归调用是函数嵌套调用的一种特殊形式
函数在调用时, 直接或间接调用了本身, 这就是递归调用
递归的本质就是循环

直接调用 : 死循环, 无意义

def f1():
    print('from f1')
    f1()
f1()    # 当超过递归最大深度时报错 "RecursionError"

间接调用

def bar():
    print('sa')
    foo()

def foo():
    print('sds')
    bar()

foo()   # 这样来回调用无意义, 当超过递归最大深度时报错 "RecursionError"

调用函数会产生 局部的名称空间，占用内存，因为上述这种调用会无休止调用本身
为了防止其无限制占用内存，python 解释器的内存管理机制对函数的递归调用做了最大的层级限制

ps : 虽然可以修改, 但应该有边界, 不可能无限制的递归, 那样无意义, 递归应分为明确的两个阶段 (回溯, 递推)

import sys
print(sys.getrecursionlimit())   # 默认 1000
sys.setrecursionlimit(2000)      # 可以改
print(sys.getrecursionlimit())   # 2000

回溯

🍔回溯就是从外向里层一层一层递归调用下去
🍔回溯阶段必须要有一个明确的结束条件
🍔每次进入下一次递归时, 问题的规模应该减少, 否则单纯的无限的递归毫无意义

递推

🍔递推就是从里到外一层一层结束递归

示例

🔰 " 回溯阶段 "
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

递归一定要有一个明确的结束条件(必须在满足某种条件下结束)
每次进入下一次递归, 问题的规模都应该减少
在 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

算法是高效解决问题的方法
二分法就是一种算法

想要从一个从小到大排列的成千上万个值中找到指定的值
如果使用遍历的话效率太低
那么二分法就可以极大的缩小问题的规模, 以次来提高效率

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!

正文完