我们在前面的章节中,很多次的看到了在函数中调用别的函数的情况。如果一个函数在内部调用了自身,这个函数就被称为递归函数。
What?函数可以自己调用自己?那不是成为了“衔尾蛇”?会不会进入死循环,永远退出不了?我们先看一个例子,典型的高斯求和问题,1+2+3+4+…+99+100,不使用递归的话,我们可以用循环,这么做:
def sum_number(n): total = 0 for i in range(1, n+1): total += i return total sum_number(100)
但如果使用递归函数来写,是这样的:
def sum_number(n): if n <= 0: return 0 return n+sum_number(n-1) sum_number(100)
分析一下代码,当n小于等于0的时候,直接给出和值为0,这句不能省。当n大于0时,结果是n加上sum_number(n-1)
。这里的sum_number(n-1)
又是一次sum_number
函数的调用,不过参数的值变成了n-1,要得sum_number(n)
到的值就必须等待sum_number(n-1)
的值被计算出来,同样要得到sum_number(n-1)
的值必须等待sum_number(n-2)
的值,如此一路推算下去,直到sum_number(0)
,因为if语句的存在,它不需要等待sum_number(-1)
的计算了,而是直接给出结果0。然后程序一路返回,直到回到最初的sum_number(n)
,并给出最终结果。
递归最核心的思想是:每一次递归,整体问题都要比原来减小,并且递归到一定层次时,要能直接给出结果!
每一个递归程序都遵循相同的基本步骤:
1.初始化算法。递归程序通常需要一个开始时使用的种子值(seed value)。可以向函数传递参数,或者提供一个入口函数,这个函数是非递归的,但可以为递归计算设置种子值。
2.检查要处理的当前值是否已经与基线条件相匹配(base case)。如果匹配,则进行处理并返回值。
3.使用更小的或更简单的子问题(或多个子问题)来重新定义答案。
4.对子问题运行算法。
5.将结果合并入答案的表达式。
6.返回结果。
递归函数的优点是定义简单,代码量少,逻辑清晰。理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。
可是,有同学会问,从上面的例子来看,我一点没觉得递归有多简单,反倒更难理解。那么请看下面的例子:
如果有这么一个树形结构的评论系统(博主的博客评论系统):
1--直接对文章的评论 1.1--对评论1的回复 1.1.1--对评论1.1的回复 1.1.2--对评论1.1的回复 1.1.3--对评论1.1的回复 1.2 --对评论1的回复 1.2.1--对评论1.2的回复 1.3 --对评论1的回复 2--直接对文章的评论 2.1 --对评论2的回复 2.1.1--对评论2.1的回复 2.2 --对评论2的回复 3--直接对文章的评论 4--直接对文章的评论
请一定要注意,其中的1.1.1
这种是方便大家理解评论层次,并不是真正的评论内容。每一个评论都有一个指向父评论的指针。现在的要求是,将所有的评论,根据评论的关系,放入一个列表内,然后逐一打印出来。需求的关键是我们必须穷举每个评论的子评论。下面我们写一个用循环来实现的伪代码:
lis = [] all_top_comments = ["顶级评论1","顶级评论2","顶级评论3","....."] for comment in all_top_comments: for child_comment in comment: for child_child_comment in child_comment: for child_child_child_comment in child_child_comment: # ....子评论的子评论的子评论的.... # 很快你就没办法写下去了,这种代码必定会被老板“重视”
你知道评论嵌套层级会有几层?有100层你就写100个for循环?对于这种问题,循环的做法是不行的。但是用递归就很简单了。
lis = [] all_top_comments = ["顶级评论1","顶级评论2","顶级评论3","....."] def get_comment(comments): for comment in comments: lis.append(comment) child_comments = comment.child() # 假设有一个child方法获取当前评论的所有子评论。 if len(child_comments) > 0: # 如果有子评论的话,就递归查找下去,否则回退 get_comment(child_comments) get_comment(all_top_comments)
本博客的评论系统就是这么写的。
使用递归函数需要注意防止递归深度溢出,在Python中,通常情况下,这个深度是1000层,超过将抛出异常。在计算机中,函数递归调用是通过栈(stack)这种数据结构实现的,每当进入一个递归时,栈就会加一层,每当函数返回一次,栈就会减一层。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。
我觉得递归函数的价值:提供跟while和for 正向迭代顺序的反向的迭代顺序。
非也,for循环与递归函数的相似度有80%多以上
def sum_number(n): total = 0 for i in range(1, n+1): total += i return total result = sum_number(100) print(result)
不错
虽然有说递归都可以用循环实现.....但,这个评论系统拿循环能写吐了,类似的还有对某个盘的文件进行遍历.并且给出目录. 另外python的递归深度可以进行修改.递归比较影响性能. --------------分割线------------ 博主要是在增加点尾递归的介绍就好了,前两天刚研究了下这个东西.......
多数编程语言没有针对尾递归做优化,Python解释器也没有做优化,所以。。。
1
2
3
4
牛
哈哈,厉害
牛啊牛啊