1. 什么是递归?
递归是一种函数调用自身的技术,它可以将一个大问题分解成几个小问题来解决,然后将小问题的解汇总起来得到最终的解。
递归分为两种情况:
递归出口:当满足某些条件时,递归将不再继续
递归调用:当不满足递归出口条件时,函数将自己调用自己,并且将问题的规模缩小
2. Python3函数中的递归
Python3允许函数调用自身,这使得在函数中使用递归成为可能。一个函数调用自身,就称为递归函数。
2.1 递归函数的定义形式
def recursion_function(arguments):
if exit_condition:
return exit_value
else:
return recursion_function(modified_arguments)
其中:
recursion_function
是递归函数的名称
arguments
是传入的参数
exit_condition
是递归出口的条件
exit_value
是退出递归时的返回值
modified_arguments
是函数调用自身时传入的新参数
2.2 Python3中的递归函数示例
计算阶乘:
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
因为阶乘的运算方式是:n! = n * (n-1) * (n-2) * … * 1
,所以递归函数就可以将计算阶乘的问题分解成了计算n-1
的阶乘。当n==1
时,退出递归并返回1
。
3. 递归函数的实际应用
3.1 在树形结构中查找元素
在树形结构中查找元素是递归函数的典型应用。下面是一个实现在树形结构中查找元素的递归函数:
def find_element(element, tree):
if tree is None:
return False
elif tree.get_value() == element:
return True
else:
return find_element(element, tree.get_left_child()) or find_element(element, tree.get_right_child())
其中,tree
是一个二叉搜索树,tree.get_value()
返回树的节点值,tree.get_left_child()
和tree.get_right_child()
返回左右子树。
递归函数首先检查是否到达了树的末端(空树),如果是,则返回False
。如果当前节点值等于需要查找的元素,则返回True
。否则,递归查找左右子树,如果其中一棵子树返回True
,则整个函数返回True
,否则返回False
。
3.2 在图形结构中搜索路径
递归函数在图形结构中搜索路径的问题中也能得到简单而有效的解决。下面是一个实现在图形结构中搜索路径的递归函数:
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if start not in graph:
return None
for node in graph[start]:
if node not in path:
new_path = find_path(graph, node, end, path)
if new_path:
return new_path
return None
其中,graph
是一个字典,字典的键值对表示图中边的关系;start
和end
是图中的节点。
递归函数的基本思路是:从初始节点开始,将当前节点加入路径并继续搜索通过邻居节点到达终点的路径。如果找到了,函数将返回路径。否则,递归搜索当前节点并检查是否存在一条路径可以到达目标节点。如果找到一条这样的路径,函数将返回路径。如果到达了一条死路,函数将返回None
并开始回溯。
3.3 在排序算法中使用递归
在排序算法中递归的应用是非常普遍的,快速排序和归并排序都可以使用递归实现。
3.3.1 快速排序
快速排序是一种使用了分治策略的排序算法。该算法首先选择一个元素作为基准值,然后将原序列分成两个子序列,一部分小于基准值,另一部分大于基准值。接下来,分别对子序列进行递归地快速排序。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [i for i in arr[1:] if i < pivot]
right = [i for i in arr[1:] if i >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
递归函数首先检查数组是否为空或只包含一个元素,如果是,则返回原数组。然后选定数组的第一个元素作为基准值。将这个元素从原数组中移除,并将原数组分成两个子序列。左子序列包含比基准值小的元素,右子序列包含比基准值大的元素。接下来,对左右子序列分别进行递归排序,并将结果合并为一个新数组。
3.3.2 归并排序
归并排序是一种使用了分治策略的排序算法。该算法将原数组分成两个长度相等的子数组,然后对两个子数组进行递归排序。当子数组排序好了,将它们合并成一个有序数组。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
递归函数首先检查序列是否为空或只包含一个元素,如果是,则返回原序列。然后,将原序列分成两个长度相等的子序列。将两个子序列递归地排序,然后将它们合并起来形成一个有序序列。
4. 递归函数的优缺点
4.1 递归函数的优点
可以使代码更加简洁易读
非常适合处理递归性质的问题
可以避免使用循环而导致的代码重复和逻辑混乱
4.2 递归函数的缺点
递归函数的性能通常较低,因为它们需要反复调用自身
在处理非递归性质的问题时,递归可能会显得非常笨拙
容易造成栈溢出,因为每一次递归都会在内存中增加一层栈
5. 总结
递归是一种函数调用自身的技术,它可以将一个大问题分解成几个小问题来解决,然后将小问题的解汇总起来得到最终的解。Python3允许函数调用自身,这使得在函数中使用递归成为可能。Python3的递归函数的基本形式为:递归出口 + 递归调用。递归函数可以被广泛地应用,在树形结构中查找元素、在图形结构中搜索路径、排序算法等领域都得到了广泛使用。虽然递归函数可以使代码简洁易读,但它也有一些缺点,如性能较低、可能造成栈溢出等。