查看: 54|回复: 0

Python—递归函数

[复制链接]
发表于 2020-2-16 05:50:24 | 显示全部楼层 |阅读模式
楔子
在讲今天的内容之前,我们先来讲一个故事,讲的什么呢?从前有座山,山里有座庙,庙里有个老僧人讲故事,讲的什么呢?从前有座山,山里有座庙,庙里有个老僧人讲故事,讲的什么呢?从前有座山,山里有座庙,庙里有个老僧人讲故事,讲的什么呢?从前有座山,山里有座庙,庙里有个老僧人讲故事,讲的什么呢......这个故事你们不喊停我能讲一天!我们说,生活中的例子也能被写成程序,刚刚这个故事,让你们写,你们怎么写呀?
  1. while True:    story = "    从前有个山,山里有座庙,庙里老僧人讲故事,    讲的什么呢?       "    print(story)
复制代码
你肯定是要这么写的,但是,如今我们已经学了函数了,什么东西都要放到函数里去调用、实验。于是你肯定会说,我就这么写:
  1. def story():    s = """    从前有个山,山里有座庙,庙里老僧人讲故事,    讲的什么呢?    """    print(s)    while True:    story()
复制代码
但是大家来看看,我是怎么写的!
  1. def story():    s = """    从前有个山,山里有座庙,庙里老僧人讲故事,    讲的什么呢?    """    print(s)    story()    story()
复制代码
先不管函数最后的报错,除了报错之外,我们能看的出来,这一段代码和上面的代码实验结果是一样的。
初识递归

递归的界说——在一个函数里再调用这个函数本身
如今我们已经大概知道刚刚讲的story函数做了什么,就是在一个函数里再调用这个函数本身,这种魔性的使用函数的方式就叫做递归
刚刚我们就已经写了一个最简单的递归函数。
递归的最大深度——997
正如你们刚刚看到的,递归函数如果不受到外力的阻止会不停实验下去。但是我们之前已经说过关于函数调用的题目,每一次函数调用都会产生一个属于它自己的名称空间,如果不停调用下去,就会造成名称空间占用太多内存的题目,于是python为了杜绝此类现象,逼迫的将递归层数控制在了997(只要997!你买不了吃亏,买不了上当...).
拿什么来证实这个“997理论”呢?这里我们可以做一个实验:
  1. def foo(n):    print(n)    n += 1    foo(n)foo(1)
复制代码
由此我们可以看出,未报错之前能看到的最大数字就是997.固然了,997是python为了我们程序的内存优化所设定的一个默认值,我们固然还可以通过一些手段去修改它:
  1. import sysprint(sys.setrecursionlimit(100000))
复制代码
我们可以通过这种方式来修改递归的最大深度,刚刚我们将python答应的递归深度设置为了10w,至于实际可以到达的深度就取决于计算机性能了。不过我们还是不保举修改这个默认的递归深度,因为如果用997层递归都没有解决的题目要么是不适合使用递归来解决要么是你代码写的太烂了~~~
看到这里,你大概会觉得递归也并不是多么好的东西,不如while True好用呢!然而,江湖上流传这如许一句话叫做:人明白循环,神明白递归。以是你可别小看了递归函数,许多人被拦在大神的门槛外这么多年,就是因为没能意会递归的真谛。而且之后我们学习的许多算法都会和递归有关系。来吧,只有学会了才有资本嫌弃!
再谈递归

这里我们又要举个例子来阐明递归能做的事情。
例一:
如今你们问我,alex老师多大了?我说我不告诉你,但alex比 egon 大两岁。
你想知道alex多大,你是不是还得去问egon?egon说,我也不告诉你,但我比武sir大两岁。
你又问武sir,武sir也不告诉你,他说他比金鑫大两岁。
那你问金鑫,金鑫告诉你,他40了。。。
这个时间你是不是就知道了?alex多大?
1金鑫  40
2武sir  42
3egon  44
4alex   46
你为什么能知道的?
首先,你是不是问alex的年龄,结果又找到egon、武sir、金鑫,你挨个儿问过去,不停到拿到一个确切的答案,然后顺着这条线再找回来,才得到终极alex的年龄。这个过程已经非常靠近递归的头脑。我们就来详细的我分析一下,这几个人之间的规律。
  1. age(4) = age(3) + 2 age(3) = age(2) + 2age(2) = age(1) + 2age(1) = 40
复制代码
那如许的情况下,我们的函数应该怎么写呢?
  1. def age(n):    if n == 1:        return 40    else:        return age(n-1)+2print(age(4))
复制代码
递归函数与三级菜单

  1. menu = {    '北京': {        '海淀': {            '五道口': {                'soho': {},                '网易': {},                'google': {}            },            '中关村': {                '爱奇艺': {},                '汽车之家': {},                'youku': {},            },            '上地': {                '百度': {},            },        },        '昌平': {            '沙河': {                '老男孩': {},                '北航': {},            },            '天通苑': {},            '回龙观': {},        },        '朝阳': {},        '东城': {},    },    '上海': {        '闵行': {            "人民广场": {                '炸鸡店': {}            }        },        '闸北': {            '火车战': {                '携程': {}            }        },        '浦东': {},    },    '山东': {},}
复制代码
menu
  1. def threeLM(dic):    while True:        for k in dic:print(k)        key = input('input>>').strip()        if key == 'b' or key == 'q':return key        elif key in dic.keys() and dic[key]:            ret = threeLM(dic[key])            if ret == 'q': return 'q'threeLM(menu)
复制代码
递归函数实现三级菜单还记得之前写过的三级菜单作业么?如今咱们用递归来写一下~
  1. l = [menu]while l:    for key in l[-1]:print(key)    k = input('input>>').strip()   # 北京    if k in l[-1].keys() and l[-1][k]:l.append(l[-1][k])    elif k == 'b':l.pop()    elif k == 'q':break
复制代码
堆栈实现递归函数与二分查找算法

http://www.cnblogs.com/Eva-J/articles/7197403.html

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?用户注册

x

天涯海角也要找到Ni:Python—递归函数

中发现Ni: Python—递归函数
中发现Ni: Python—递归函数
中发现Ni: Python—递归函数
中发现Ni: Python—递归函数
中发现Ni: Python—递归函数
中发现Ni: Python—递归函数
相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表