Hexo
0%

39、递归.md

Posted on In

一、概要

在调用一个函数的过程中，直接或间接地调用了函数本身这个就叫递归

注：Python在递归中没有像别的语言对递归进行优化，所以他的每一次调用都会基于上一次的调用进行，并且他设置了最大的递归数量防止递归外溢,python默认的递归深度是很有限的，不能超过1000，当递归深度超过这个值的时候，就会引发这样的一个异常。
解决的方式是手工设置递归调用深度，方式为

1
2
import sys   
sys.setrecursionlimit(1000000) #例如这里设置为一百万

需要注意以下几点：

  • 递归就是在过程或函数里调用自身
  • 必须有一个明确的递归结束条件，称为递归出口。

二、示例代码

  1. 代码

    1
    2
    3
    4
    def func():
        print('from func')
        func()
    func()
    1
    2
    3
    4
    5
    6
    7
    8
    #间接调用自己
    def fun1():
        print('from foo')
        fun2()
    def fun2():
        print('from bar')
        fun1()
    fun1()

  2. 阶乘

    1
    2
    3
    4
    5
    def factorial(n):
         result = 1
         for i in range(2, n+1):
             result *= i
         return result
    1
    2
    3
    4
    5
    6
    #递归实现
    def fun(n):
         if n == 1:
             return 1
         else:
            return n * fun(n - 1)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    factorial(5)                        # 第 1 次调用使用 5
    5 * factorial(4)                    # 第 2 次调用使用 4
    5 * (4 * factorial(3))              # 第 3 次调用使用 3
    5 * (4 * (3 * factorial(2)))        # 第 4 次调用使用 2
    5 * (4 * (3 * (2 * factorial(1))))  # 第 5 次调用使用 1 
    5 * (4 * (3 * (2 * 1)))             # 从第 5 次调用返回
    5 * (4 * (3 * 2))                   # 从第 4 次调用返回
    5 * (4 * 6)                         # 从第 3次调用返回
    5 * 24                              # 从第 2 次调用返回
    120                                 # 从第 1 次调用返回

    优点

    • 递归使代码看起来更加整洁、优雅
    • 可以用递归将复杂任务分解成更简单的子问题
    • 使用递归比使用一些嵌套迭代更容易

    缺点

    • 递归的逻辑很难调试、跟进
    • 递归调用的代价高昂（效率低），因为占用了大量的内存和时间。

  3. 递归遍历列表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # 通过递归遍历list
    data_list = ["aaa", "bbb", "ccc", "ddd", ["qqq", "sss", ["mmm", "rrr", ["tt", "ccs"]]]]
    def print_list(list_nums):
        for item in list_nums:
            if isinstance(item, list):
                print_list(item)
            else:
                print(item)

    print_list(data_list)

  4. 递归遍历文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def get_files(root):
        files = os.listdir(root)
        for file_name in files:
            file_path = os.path.join(root, file_name)
            if os.path.isdir(file_path):
                print("目录：", file_path)
                get_files(file_path)
            else:
                print("普通文件", file_name)