软件测试笔记｜Python编程基础｜Python函数语法之递归函数

“动动小手，点点关注呗～”

一件东西破了就是破了，我宁愿把它丢掉，回忆着它的美好，也不愿意整天看着残破的它伤心。——《飘（经典译林）》

一、引言

在Python编程的奇妙世界里，函数是我们实现各种逻辑的得力工具。而递归函数，作为一种特殊且强大的函数类型，以其独特的自我调用机制，为解决特定类型的问题提供了优雅而高效的解决方案。递归函数的思想深邃而迷人，它在数学、计算机科学等多个领域都有着广泛的应用。无论是计算阶乘、处理树形结构，还是进行复杂的算法设计，递归函数都能大显身手。接下来，让我们一同深入探索Python函数语法中的递归函数。

二、什么是递归函数

2.1 递归函数的定义

递归函数是指在函数的定义中调用自身的函数。简单来说，就是一个函数内部包含了对自身的调用语句。这种自我调用的方式形成了一种层层嵌套的执行结构，就像俄罗斯套娃一样，一层套着一层。例如，计算阶乘的递归函数：

在这个factorial函数中，当n大于1时，函数会调用自身factorial(n - 1)，并将结果与n相乘返回。

• 函数定义：第1行def factorial(n):，定义了一个名为factorial的函数，该函数接受一个参数n。

• 终止条件：第2行到第3行if n == 0 or n == 1:，判断传入的参数n是否等于0或者1。在数学中，0的阶乘和1的阶乘都定义为1，所以当n为0或1时，函数直接返回1，这是递归的终止条件。

• 递归调用：第4行到第5行else:后面的代码块，当n大于1时，执行return n * factorial(n - 1)。这里使用了递归的方式，用n乘以n-1的阶乘，n-1的阶乘又会继续调用factorial函数，不断递归，直到满足终止条件，从而实现计算n的阶乘的功能。

例如，如果调用factorial(5)，计算过程如下：

• factorial(5)会返回5 * factorial(4)；

• factorial(4)会返回4 * factorial(3)；

• factorial(3)会返回3 * factorial(2)；

• factorial(2)会返回2 * factorial(1)；

• 因为factorial(1)满足终止条件，返回1，然后依次回代计算，最终得到5 * 4 * 3 * 2 * 1 = 120。

2.2 递归函数的基本原理

递归函数的执行依赖于两个关键要素：基线条件（base case）和递归条件（recursive case）。

• 基线条件：是递归结束的条件，它确保递归不会无限进行下去，避免陷入死循环。在上述阶乘的例子中，n == 0 or n == 1就是基线条件，当满足这个条件时，函数直接返回1，不再进行递归调用。

• 递归条件：定义了函数如何通过自我调用逐步接近基线条件。在阶乘函数中，n * factorial(n - 1)就是递归条件，它通过不断减小n的值，逐渐逼近基线条件。

三、递归函数的语法详解

3.1 递归函数的结构

一个典型的递归函数通常包含以下几个部分：

• 函数定义：使用def关键字定义函数，指定函数名和参数列表。

• 基线条件判断：通过if语句判断是否满足基线条件，如果满足则返回特定值，结束递归。

• 递归调用：在不满足基线条件时，函数内部调用自身，并传递适当的参数，以便逐步逼近基线条件。

3.2 参数传递与返回值

在递归调用过程中，参数的传递起着关键作用。每次递归调用时，参数的值都会发生变化，以逐渐接近基线条件。同时，递归函数的返回值也会在递归调用的过程中层层传递，最终得到整个递归计算的结果。例如，计算斐波那契数列的递归函数：

在这个函数中，n作为参数在每次递归调用时不断减小。返回值则通过递归调用的层层计算和传递，最终得到第n个斐波那契数。

• 函数定义：第1行def fibonacci(n):定义了一个名为fibonacci的函数，接受一个参数n ，用于指定要计算斐波那契数列中的第几项。

• 终止条件：

◦ 第2行到第3行if n == 0:，当传入的参数n等于0时，返回0 ，因为斐波那契数列的第0项定义为0。

◦ 第4行到第5行elif n == 1:，当n等于1时，返回1，斐波那契数列的第1项是1。这两个条件是递归的终止条件。

• 递归调用：第6行到第7行else:后面的代码块，当n大于1时，通过递归调用fibonacci(n - 1)和fibonacci(n - 2)，并将这两个结果相加。因为斐波那契数列从第2项开始，每一项都等于前两项之和，所以这样可以计算出第n项的值。

举例运行结果

假设调用fibonacci(6)，计算过程如下：

即fibonacci(6)的结果是8 。

四、递归函数的应用场景

4.1 数学计算

递归函数在数学计算领域有着广泛的应用，除了前面提到的阶乘和斐波那契数列，还可以用于计算最大公约数（欧几里得算法）：

这个递归函数通过不断将较大数除以较小数取余数，再将较小数和余数作为新的参数进行递归调用，直到余数为0，此时的较小数就是最大公约数。

• 函数定义：第1行def gcd(a, b):定义了一个名为gcd的函数，接受两个参数a和b，用来计算这两个数的最大公约数。

• 终止条件：第2行到第3行if b == 0:，当参数b的值为0时，说明此时a就是最大公约数，直接返回a。这是递归的终止条件，因为任何数和0的最大公约数就是这个数本身。

• 递归调用：第4行到第5行else:后面的代码块，当b不为0时，通过递归调用gcd(b, a % b)来更新a和b的值。这里a % b表示a除以b的余数。欧几里得算法的核心思想是两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数，不断重复这个过程，直到余数为0 。

举例运行结果

假设调用gcd(24, 18)，计算过程如下：

• 第一次调用：初始a = 24，b = 18，b不为0，执行gcd(18, 24 % 18)，即gcd(18, 6)。

• 第二次调用：此时a = 18，b = 6，b不为0，执行gcd(6, 18 % 6)，即gcd(6, 0)。

• 第三次调用：此时a = 6，b = 0，满足终止条件，返回a，也就是6。

所以，gcd(24, 18)的结果是6 。

4.2 树形结构遍历

在处理树形数据结构时，递归函数能够轻松实现深度优先遍历（DFS）。例如，遍历一个简单的树节点类：

在这个例子中，dfs函数通过递归调用自身，实现了对树中每个节点的深度优先遍历，打印出每个节点的值。

1. 定义树节点类 TreeNode：

◦ 第1行到第5行定义了一个名为TreeNode的类，用于表示树的节点。

◦ 第2行的__init__方法是类的构造函数，接受一个参数value，用于初始化节点的值。

◦ 第3行将传入的value赋值给节点的self.value属性。

◦ 第4行创建一个空列表self.children，用于存储该节点的子节点。

2. 定义深度优先搜索函数 dfs：

◦ 第7行到第12行定义了dfs函数，用于对树进行深度优先搜索。

◦ 第8行的if node:判断当前节点是否为空，如果不为空则继续执行。

◦ 第9行print(node.value)打印当前节点的值。

◦ 第10行到第11行的for循环遍历当前节点的所有子节点，并对每个子节点递归调用dfs函数，从而实现深度优先搜索。

3. 创建树结构并调用搜索函数：

◦ 第15行创建了根节点root，值为1。

◦ 第16行和第17行分别创建了两个子节点child1（值为2）和child2（值为3）。

◦ 第18行将child1和child2添加为根节点root的子节点。

◦ 第19行给child1添加了两个子节点（值分别为4和5）。

◦ 第21行调用dfs(root)，从根节点开始对整个树进行深度优先搜索。

运行过程

1. 程序开始执行，首先定义了 TreeNode 类和 dfs 函数。

2. 创建树结构：

◦ 创建根节点 root，值为1。

◦ 创建子节点 child1 和 child2，值分别为2和3，并将它们添加为 root 的子节点。

◦ 为 child1 创建子节点，值为4和5。

3. 调用 dfs(root) 开始深度优先搜索：

◦ 首先访问根节点 root，打印其值1。

◦ 然后遍历 root 的子节点，先访问 child1，打印其值2。

◦ 接着遍历 child1 的子节点，分别访问值为4和5的节点，依次打印4和5。

◦ 访问完 child1 的子树后，回到 root，访问 child2，打印其值3。

◦ 由于 child2 没有子节点，深度优先搜索结束。

运行这段代码后，控制台会按照深度优先搜索的顺序打印出树中每个节点的值，结果如下：

4.3 分治算法

递归是实现分治算法的重要手段。分治算法的思想是将一个大问题分解成若干个规模较小的子问题，然后分别解决这些子问题，最后将子问题的解合并得到原问题的解。例如，归并排序算法就是典型的分治算法，使用递归实现如下：

在merge_sort函数中，通过递归将数组不断分割成两半，直到数组长度为1或0（基线条件），然后再通过merge函数将分割后的子数组合并成有序数组。

1. merge_sort函数：

◦ 第1行到第8行定义了merge_sort函数，用于对列表进行归并排序。

◦ 第2行if len(arr) <= 1:判断传入的列表arr长度是否小于等于1，如果是，说明列表已经有序，直接返回该列表，这是递归的终止条件。

◦ 第4行mid = len(arr) // 2计算列表的中间位置。

◦ 第5行left = merge_sort(arr[:mid])对列表的左半部分进行递归排序。

◦ 第6行right = merge_sort(arr[mid:])对列表的右半部分进行递归排序。

◦ 第7行return merge(left, right)将排好序的左右两部分进行合并。

2. merge函数：

◦ 第10行到第22行定义了merge函数，用于合并两个已排序的列表。

◦ 第11行result = []创建一个空列表，用于存储合并后的结果。

◦ 第12行i = j = 0初始化两个指针，分别指向left和right列表的起始位置。

◦ 第13行到第19行的while循环，在left和right列表都未遍历完的情况下，比较两个指针指向的元素大小，将较小的元素添加到result中，并将对应指针后移一位。

◦ 第20行result.extend(left[i:])将left列表中剩余的元素添加到result中。

◦ 第21行result.extend(right[j:])将right列表中剩余的元素添加到result中。

◦ 第22行return result返回合并后的有序列表。

举例运行结果

假设调用merge_sort([3, 1, 4, 1, 5, 9, 2, 6])，计算过程如下：

• 首先通过递归将列表不断拆分，直到每个子列表长度为1。

• 然后开始合并：

◦ 合并[3]和[1]得到[1, 3]；合并[4]和[1]得到[1, 4]；合并[5]和[9]得到[5, 9]；合并[2]和[6]得到[2, 6]。

◦ 接着合并[1, 3]和[1, 4]得到[1, 1, 3, 4]；合并[5, 9]和[2, 6]得到[2, 5, 6, 9]。

◦ 最后合并[1, 1, 3, 4]和[2, 5, 6, 9]得到[1, 1, 2, 3, 4, 5, 6, 9]。

所以，merge_sort([3, 1, 4, 1, 5, 9, 2, 6])的结果是[1, 1, 2, 3, 4, 5, 6, 9] 。

五、递归函数的优缺点

5.1 优点

• 代码简洁：递归函数能够用简洁的代码表达复杂的逻辑，尤其是在处理具有递归性质的问题时，代码结构清晰，易于理解和维护。

• 符合思维习惯：对于一些具有递归特性的问题，如树形结构遍历、分治算法等，使用递归函数的思路与人类的思维方式较为契合，能够更自然地解决问题。

5.2 缺点

• 性能问题：递归函数在执行过程中会不断调用自身，这会导致函数调用栈不断增加，占用大量的内存空间。当递归深度过大时，可能会导致栈溢出错误（Stack Overflow Error）。

• 调试困难：由于递归函数的执行过程较为复杂，层层嵌套的调用关系使得调试过程变得困难，难以追踪函数的执行路径和变量的变化情况。

六、递归函数的优化与替代方案

6.1 尾递归优化

尾递归是一种特殊的递归形式，在递归调用返回时，不再进行任何额外的操作，直接返回递归调用的结果。Python本身并不支持自动的尾递归优化，但我们可以通过手动改写代码来模拟尾递归优化的效果。例如，改写阶乘函数为尾递归形式：

在这个版本中，acc作为累加器，在每次递归调用时将当前的n与acc相乘并传递下去，避免了递归调用返回后再进行乘法操作，从而减少了栈空间的占用。

1. 辅助函数 factorial_helper：

◦ 第1行def factorial_helper(n, acc=1):定义了一个名为factorial_helper的辅助函数，它接受两个参数，n表示要计算阶乘的数，acc是累加器，默认值为1。

◦ 第2行到第3行if n == 0 or n == 1:，判断n是否为0或1。在数学中，0的阶乘和1的阶乘都为1，此时直接返回累加器acc的值，这是递归的终止条件。

◦ 第4行到第5行else:后面的代码块，当n大于1时，通过递归调用factorial_helper(n - 1, acc * n)来更新n和acc的值。每次递归，n减1，acc乘以当前的n，逐步累乘计算阶乘。

2. 主函数 factorial：

◦ 第7行def factorial(n):定义了名为factorial的主函数，接受一个参数n。

◦ 第8行return factorial_helper(n)，在主函数中直接调用辅助函数factorial_helper，将n传入，开始阶乘的计算过程，这样可以为用户提供一个更简洁的调用接口。

举例运行结果

假设调用factorial(5)，计算过程如下：

• 第一次调用factorial_helper(5, 1)，n为5，不满足终止条件，继续递归调用factorial_helper(4, 1 * 5)。

• 第二次调用factorial_helper(4, 5)，n为4，不满足终止条件，继续递归调用factorial_helper(3, 5 * 4)。

• 第三次调用factorial_helper(3, 20)，n为3，不满足终止条件，继续递归调用factorial_helper(2, 20 * 3)。

• 第四次调用factorial_helper(2, 60)，n为2，不满足终止条件，继续递归调用factorial_helper(1, 60 * 2)。

• 第五次调用factorial_helper(1, 120)，n为1，满足终止条件，返回acc的值120。

所以，factorial(5)的结果是120 。

6.2 使用迭代替代递归

对于一些递归问题，我们可以使用迭代的方式来解决，迭代方式通常不会受到栈深度的限制，性能更优。例如，使用迭代方式计算阶乘：

• 函数定义：第1行def factorial(n):，定义了一个名为factorial的函数，它接受一个参数n，这个函数的功能是计算n的阶乘。

• 初始化结果变量：第2行result = 1，创建了一个名为result的变量，并初始化为1，这个变量用于存储阶乘的计算结果。因为任何数乘以1结果不变，所以从1开始累乘。

• 循环计算阶乘：第3行for i in range(1, n + 1):，使用for循环，range(1, n + 1)会生成一个从1到n的整数序列（包含1和n）。在每次循环中，变量i会依次取这个序列中的值。

• 累乘操作：第4行result *= i ，等同于result = result * i，即把result与当前的i相乘，不断累乘，从而实现计算阶乘的功能。

• 返回结果：第5行return result，当循环结束后，result中存储的就是n的阶乘值，将其返回。

举例运行结果

假设调用factorial(4)：

• 第一次循环，i = 1，result = 1 * 1 = 1。

• 第二次循环，i = 2，result = 1 * 2 = 2。

• 第三次循环，i = 3，result = 2 * 3 = 6。

• 第四次循环，i = 4，result = 6 * 4 = 24。

循环结束后，返回result的值24，所以factorial(4)的结果是24 。

这种迭代方式通过循环实现了与递归相同的功能，但避免了递归带来的性能和栈溢出问题。

七、总结

递归函数作为Python函数语法中的重要组成部分，以其独特的自我调用机制为我们解决各种复杂问题提供了有力的工具。通过深入理解递归函数的定义、原理、语法以及应用场景，我们能够在编程中巧妙地运用递归思想，编写出简洁而优雅的代码。然而，我们也要清楚地认识到递归函数的优缺点，在实际应用中根据具体情况选择合适的解决方案，必要时进行优化或采用替代方案。希望通过本文的介绍，你对Python中的递归函数有了更全面、深入的理解和掌握，能够在未来的编程道路上灵活运用递归函数，攻克各种编程难题。

“动动小手，点点关注呗～”🫰