35 函数递归与二分法

189次阅读
没有评论

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

一. 函数递归

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!
正文完
 
shawn
版权声明:本站原创文章,由 shawn 2023-06-16发表,共计1525字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)