Python 简明教程
Python - Recursion
递归是一个基本编程概念，其中函数自身调用自身来解决问题。此技术将一个复杂问题分解为更小且更可管理的相同类型的子问题。在 Python 中，递归通过定义一个函数在自身函数体内进行一个或多个自身调用来实现。
Components of Recursion
正如我们前面讨论的那样，递归是一个函数自身调用的技术。此处为了理解递归，需要了解其关键组件。以下是递归的主要组件 −
-
Base Case
-
Recursive Case
Base Case
基本情况是递归中的基本概念，如果用作递归函数停止自身调用的条件。它对于防止无限递归和随后的栈溢出错误至关重要。
基本情况为问题最简单的实例提供了一个直接解决方案，确保每次递归调用都更接近于终止条件。
递归最流行的例子是阶乘的计算。数学上阶乘定义为 -
n! = n × (n-1)!可以看出，我们使用阶乘本身来定义阶乘。因此，这是一个编写递归函数的合适案例。让我们展开以上定义以计算 5 的阶乘值。
5! = 5 × 4!
5 × 4 × 3!
5 × 4 × 3 × 2!
5 × 4 × 3 × 2 × 1!
5 × 4 × 3 × 2 × 1
= 120虽然我们可以使用循环执行此计算，但其递归函数涉及通过递减数字依次调用它，直到数字变为 1。
以下示例显示了如何使用递归函数计算阶乘 -
def factorial(n):
if n == 1:
print (n)
return 1 #base case
else:
print (n,'*', end=' ')
return n * factorial(n-1) #Recursive case
print ('factorial of 5=', factorial(5))上述程序生成以下输出 −
5 * 4 * 3 * 2 * 1
factorial of 5= 120Recursive Case
递归情况是递归函数的一部分，其中函数自身调用自身来解决相同问题的更小或更简单的实例。此机制允许将复杂问题分解为更可管理的子问题，其中每个问题均为原始问题的较小版本。
递归情况对于朝基本情况发展至关重要，确保递归最终会终止。
以下是递归情况的示例。在此示例中，我们生成 Fibonacci 数列，其中递归情况对前两个 Fibonacci 数的结果求和 −
def fibonacci(n):
if n <= 0:
return 0 # Base case for n = 0
elif n == 1:
return 1 # Base case for n = 1
else:
return fibonacci(n - 1) + fibonacci(n - 2) # Recursive case
fib_series = [fibonacci(i) for i in range(6)]
print(fib_series)上述程序生成以下输出 −
[0, 1, 1, 2, 3, 5]Binary Search using Recursion
二分查找算法是一种用于快速查找已排序列表中的元素的强大算法，其采用对数时间复杂度，使其非常有效。
让我们看另一个理解递归工作原理的示例。眼前的问题是检查给定数字是否存在于列表中。
虽然我们可以使用 for 循环在列表中按顺序查找某个数字并比较每个数字，但如果列表太大，顺序查找效率不高。二分查找算法检查索引“high”是否大于索引“low”。根据“mid”变量中存在的 value，再次调用该函数来搜索元素。
我们有一个按升序排列的数字列表。然后我们找到列表的中间点，并根据所需的数字是否小于或大于中间点的数字来将检查限制在中间点的左右两侧。
下图显示了二分查找的工作原理 -
Example
以下代码实现了递归二分查找技术 -
def bsearch(my_list, low, high, elem):
if high >= low:
mid = (high + low) // 2
if my_list[mid] == elem:
return mid
elif my_list[mid] > elem:
return bsearch(my_list, low, mid - 1, elem)
else:
return bsearch(my_list, mid + 1, high, elem)
else:
return -1
my_list = [5,12,23, 45, 49, 67, 71, 77, 82]
num = 67
print("The list is")
print(my_list)
print ("Check for number:", num)
my_result = bsearch(my_list,0,len(my_list)-1,num)
if my_result != -1:
print("Element found at index ", str(my_result))
else:
print("Element not found!")