递归函数

阅读: 3652


我们在前面的章节中,很多次的看到了在函数中调用别的函数的情况。如果一个函数在内部调用了自身,这个函数就被称为递归函数。

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)这种数据结构实现的,每当进入一个递归时,栈就会加一层,每当函数返回一次,栈就会减一层。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。



评论总数: 2



user_image
我是标题

虽然有说递归都可以用循环实现.....但,这个评论系统拿循环能写吐了,类似的还有对某个盘的文件进行遍历.并且给出目录. 另外python的递归深度可以进行修改.递归比较影响性能. --------------分割线------------ 博主要是在增加点尾递归的介绍就好了,前两天刚研究了下这个东西.......

user_image
尾递归

多数编程语言没有针对尾递归做优化,Python解释器也没有做优化,所以。。。