前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >day 17 - 1 递归函数

day 17 - 1 递归函数

作者头像
py3study
发布2020-01-20 16:42:32
3480
发布2020-01-20 16:42:32
举报
文章被收录于专栏:python3python3

递归函数

什么是递归

  了解什么是递归 : 在函数中调用自身函数   最大递归深度默认是 997/998 —— 是 python 从内存角度出发做得限制   能看懂递归   能知道递归的应用场景   初识递归 —— 二分法的例子   算法 —— 二分查找算法   三级菜单 —— 递归实现

我们先来看一个简单的递归函数

代码语言:javascript
复制
#可以执行下,看下与递归函数执行的结果有什么不同
while True:
    print('从前有座山')

#一个简单的递归函数
def story():
    print('从前有座山')
    story()
    print(111)  #执行不到这句话

story()


#RecursionError: maximum recursion depth exceeded while calling a Python object
# 递归的错误,超过了递归的最大深度

测试递归函数的深度

代码语言:javascript
复制
#测试以下 python 中的递归深度  默认 997

#修改递归限制
import sys
sys.setrecursionlimit(100000)  #不要改

n=0
def rec():
    global n
    print('从前有座山')
    n +=1
    print(n)
    rec()
rec()

# 如果递归次数太多,那么就不适合使用递归来解决问题
# 递归的缺点 : 占内存
# 递归的优点:  会让代码变简单

递归的逻辑

当你想解决一个问题时,需要知道另一个问题的答案 且下一个问题和前面的问题处理方法一致 递归是自上往下解决问题的

好比这样的问题

代码语言:javascript
复制
张三 多大       n = 1   age(1) = age(2)+2 = age(n+1) + 2
张三 比 李四 大两岁
李四 多大?      n = 2   age(2) = age(3) + 2 = age(n+1) +2
李四 比 王五 大两岁
王五 多大       n = 3   age(3) = age(4) + 2 = age(n+1) +2
王五 比 赵六 大两岁
赵六 多大?
赵六 40 了      n = 4   age(4) = 40

我们把上面的逻辑写一个递归函数

代码语言:javascript
复制
def age(n):
    if n == 4:
        return 40
    elif n >0 and n < 4:
        return age(n+1) + 2
print(age(1))  #输出结果 46

这个 46 是怎么产生的呢?我们下面来看

代码语言:javascript
复制
def age(1):
    if 1 == 4:
        return 40
    elif 1 > 0 and 1 < 4:
        return 46  #于是最终得到 46 的结果

def age(2):
    if 2 == 4:
        return 40
    elif 2 >0 and 2 < 4:
        return age(3) + 2    # age(3) 的返回结果加 2 得到 44,返回给 age(1)

def age(3):
    if 3 == 4:
        return 40
    elif 3 >0 and 3 < 4:
        return  age(n+1) + 2   #4、age(4) + 2 得到 42 返回给age(2)

def age(4):
    if 4 == 4:        #2、发现下面判断不在满足条件
        return 40    #3、于是返回 return 40,注意:这里返回给了调用着 age(3)
    elif n >0 and n < 4:
        return  age(n+1) + 2        #1、这里 age(3+1) 得到 age(4) ,再次调用

小结:

超过最大递归限制的报错 只要写递归函数,必须要有结束条件。

返回值 1、不要只看到return就认为已经返回了。要看返回操作是在递归到第几层的时候发生的,然后返回给了谁。 2、如果不是返回给最外层函数,调用者就接收不到。 3、需要再分析,看如何把结果返回回来。

二分查找算法

什么叫算法 计算的方法 : 人脑复杂 计算机简单

我们现在学习的算法 都是过去时   了解基础的算法 才能创造出更好的算法   不是所有的事情都能套用现成的方法解决的   有些时候会用到学过的算法知识来解决新的问题

二分查找算法 必须处理有序的列表 k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

基础版,列表的 k 的下标乱了

代码语言:javascript
复制
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def find(lis,aim):
    #获取中间值
    mid = len(lis)//2
    #如果中间值大于 aim
    if lis[mid] > aim:
        new_lis = lis[:mid]
        find(new_lis,aim)
    elif lis[mid] < aim:
        new_lis = lis[mid + 1:]
        find(new_lis,aim)
    else:
        print('找到了:'+ str(aim) + ' 所在位置为:'+ str(mid))

find(k,66)

升级版,解决了下标问题

代码语言:javascript
复制
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def find(lis,aim,start = 0,end = len(k)):
    #获取中间值
    mid = (end - start)//2 + start
    #如果中间值大于 aim
    if lis[mid] > aim:
        find(lis,aim,start = start,end = mid-1)
    elif lis[mid] < aim:
        find(lis,aim,start = mid + 1,end = end)
    else:
        print('找到了:'+ str(aim) + ' 所在位置为:',mid)

find(k,18)
find(k,43)

继续升级 end 的问题 我们不希望每次找一个列表的都要修改函数中额 len(k) 这样函数就没有了可用性

代码语言:javascript
复制
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def find(lis,aim,start = 0,end = None):
    end = len(lis) if end is None else end
    #获取中间值
    mid = (end - start) // 2 + start
    #中间值大于 aim
    if lis[mid] > aim:
        find(lis,aim,start = 0,end = mid - 1)
    elif lis[mid]< aim:
        find(lis,aim,start= mid + 1,end = end)
    else:
        print('找到了:'+str(aim)+"位于"+str(mid))
find(k,69)

接着升级 找不到所要查找的值怎么处理

代码语言:javascript
复制
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def find(lis,aim,start = 0,end = None):
    end = len(lis) if end is None else end
    #获取中间值
    mid = (end - start) // 2 + start
    if start <= end:
        #中间值大于 aim
        if lis[mid] > aim:
            find(lis,aim,start = 0,end = mid - 1)
        elif lis[mid]< aim:
            find(lis,aim,start= mid+1,end = end)
        else:
            print('找到了:'+str(aim)+"位于"+str(mid))
    else:
        print('找不到这个值')
find(k,68)

最后返回值的问题,因为我们希望最后的结果只是一个我们想要的值

代码语言:javascript
复制
k = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def find(lis,aim,start = 0,end = None):
    end = len(lis) if end is None else end
    #获取中间值
    mid = (end - start) // 2 + start
    if start <= end:
        #中间值大于 aim
        if lis[mid] > aim:
           return find(lis,aim,start = 0,end = mid - 1)
        elif lis[mid]< aim:
           return find(lis,aim,start= mid+1,end = end)
        else:
           # print('找到了:'+str(aim)+"位于"+str(mid))
           return mid
    else:
        return'找不到这个值'

print(find(k,5))

为了更加了解递归函数和上面的二分查找法可以拆开上面的函数分析下面的三种方法

代码语言:javascript
复制
# 67  发生两次调用
# 66  发生好几次
# 44  找不到
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-04-21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档