Python递归教程实例操作-XAMPP中文组官网

写在前面：小时候看动画片，好像只是图个乐呵。现在也是。

movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91,
          ["Graham Chapman", ["Michael Palin", "John Cleese",
                              "Terry Gilliam", "Eric Idle", "Terry Jones"]]]

有一个电影列表，里面包含了电影信息、主演以及助演名单，现在希望把所有信息如下图逐条打印在屏幕上，我们可以怎么做呢？

最笨的方法使用for循环一层一层的判断：

movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91,
          ["Graham Chapman", ["Michael Palin", "John Cleese",
                              "Terry Gilliam", "Eric Idle", "Terry Jones"]]]

for each_item in movies:
    if isinstance(each_item, list):
        for nested_item in each_item:
            if isinstance(nested_item, list):
                for deeper_item in nested_item:
                    print(deeper_item)
            else:
                print(nested_item)
    else:
        print(each_item)

偷懒一点的方法使用递归（重复的代码放到函数中，并在函数体内调用自己）：

def print_item(items):
    for item in items:
        if isinstance(item, list):
            print_item(item)
        else:
            print(item)


movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91,
          ["Graham Chapman", ["Michael Palin", "John Cleese",
                              "Terry Gilliam", "Eric Idle", "Terry Jones"]]]
print_item(movies)

在函数内部可以调用其他函数，也可以对自身调用，如果一个函数在函数体内调用了自己，这个函数就是递归函数。

递归包括“递和归”两个过程：

最先执行递去的过程，只要没有触发返回值和终止条件，就会一直在函数内，带着更新后的参数调用函数自身（到内部调用函数，下面的代码不会被执行，而是暂停阻塞），并且不断的在原来的基础上去向下、向内开辟新的内存空间。

一旦当前空间函数全部执行结束（达到了终止条件）或者执行到了return返回值，递去的过程就结束了，然后再一级一级的把值返回给函数调用者。

递归的特点：

1. 必须有一个明确的结束条件

2. 每次进入更深一层递归时，问题规模（计算量）相比上一次递归都会有所减少

3. 递归效率不高，递归层次过多会导致栈溢出

举个阶乘函数的例子：

N! = 1 * 2 * 3 * … * N = factorial(N)

即：

factorial(N) = N!

= N * (N-1)!

= N * (N-1) * (N-2)!

…

= N * (N-1) * (N-2) … * 3 * 2 * 1

由此可见，阶乘是递归的，因为factorial(N) = N * factorial(N-1) 。也就是说，为了获得factorial(N) 的值需要计算factorial(N-1)，为了计算factorial(N-1)需要先计算factorial(N-2)等…

递归函数为：

def factorial(n):
    """递归"""
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)


print(factorial(5))

计算factorial(5)，根据函数定义可分析出他的计算过程（最后自己打断点debug一下）：

===> factorial(5)
递的过程：
===> n=5, retrun n * factorial(n-1)  ==>  5 * factorial(4)
===> n=4, retrun n * factorial(n-1)  ==>  4 * factorial(3)
===> n=3, retrun n * factorial(n-1)  ==>  3 * factorial(2)
===> n=2, retrun n * factorial(n-1)  ==>  2 * factorial(1)
===> n=1, retrun 1
归的过程：
===> n=2, retrun 2 * factorial(2-1)  ==>  2 * 1 = 2
===> n=3, retrun 3 * factorial(2)  ==>  3 * 2 = 6
===> n=4, retrun n * factorial(n-1)  ==>  4 * 6 = 24
===> n=5, retrun 5 * factorial(5-1)  ==>  5 * 24 = 120

理论上，所有的递归函数都可以写成循环的方式，上面的例子改为使用循环实现为：

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result


print(factorial(5))

通过对比，可以发现递归函数定义简单，逻辑清晰。但是，使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一次调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，就会导致栈溢出。比如试一下factorial(1000)：

可通过尾递归优化的方法来解决递归调用栈溢出的问题，尾递归和循环的效果是一样的，所以可以把循环看成是一种特殊的尾递归函数。尾递归是指在函数返回的时候，通过调用自身本身且return语句不能包含表达式。这样编译器或解释器就可以把尾递归做优化，不管递归本身调用多少次，都只占用一个栈帧，就不会出现栈溢出的情况了。

上面的factorial(n)函数由于return n * factorial(n-1)引入了乘法表达式，所以就不会尾递归了。可以通过加一些代码，优化成尾递归的方式（将每一步的乘积传入到递归函数中）：

def factorial(n):
    """优化"""
    return fact_iter(n, 1)


def fact_iter(num, result):
    if num == 1:
        return result
    return fact_iter(num-1, num*result)


print(factorial(5))

fact(5)对应的fact_iter(5, 1)的调用如下：

===> fact_iter(5, 1)
===> fact_iter(4, 5)
===> fact_iter(3, 20)
===> fact_iter(2, 60)
===> fact_iter(1, 120)
===> 120

可以看到，return fact_iter(num – 1, num * product)仅返回递归函数本身，num – 1和num * product在函数调用前就会被计算，所以不会影响函数调用也不会导致栈溢出，但是python解释器没有做尾递归优化，因此改为尾递归方式依然会导致栈溢出。

看下这个练习，会输出什么结果呢？

Tips：注意调用函数本身的时候，下面的代码只是被暂停了哦~

def test(n):
    """递归练习"""
    print(n)
    if n > 0:
        test(n-1)
    else:
        print("-"*5)
    print(n)


print(test(3))

转载请注明：XAMPP中文组官网 » Python递归教程实例操作

Python递归教程实例操作

与本文相关的文章

您必须登录才能发表评论！

与本文相关的文章

您必须 登录 才能发表评论！

您必须登录才能发表评论！