Python 简明教程

Python - Recursion

递归是一个基本编程概念，其中函数自身调用自身来解决问题。此技术将一个复杂问题分解为更小且更可管理的相同类型的子问题。在 Python 中，递归通过定义一个函数在自身函数体内进行一个或多个自身调用来实现。

Recursion is a fundamental programming concept where a function calls itself in order to solve a problem. This technique breaks down a complex problem into smaller and more manageable sub-problems of the same type. In Python, recursion is implemented by defining a function that makes one or more calls to itself within its own body.

Components of Recursion

正如我们前面讨论的那样，递归是一个函数自身调用的技术。此处为了理解递归，需要了解其关键组件。以下是递归的主要组件 −

As we discussed before Recursion is a technique where a function calls itself. Here for understanding recursion, it’s required to know its key components. Following are the primary components of the recursion −

  1. Base Case

  2. Recursive Case

Base Case

基本情况是递归中的基本概念，如果用作递归函数停止自身调用的条件。它对于防止无限递归和随后的栈溢出错误至关重要。

The Base case is a fundamental concept in recursion, if serving as the condition under which a recursive function stops calling itself. It is essential for preventing infinite recursion and subsequent stack overflow errors.

基本情况为问题最简单的实例提供了一个直接解决方案，确保每次递归调用都更接近于终止条件。

The base case provides a direct solution to the simplest instance of the problem ensuring that each recursive call gets closer to this terminating condition.

递归最流行的例子是阶乘的计算。数学上阶乘定义为 -

The most popular example of recursion is calculation of factorial. Mathematically factorial is defined as −

n! = n × (n-1)!

可以看出，我们使用阶乘本身来定义阶乘。因此，这是一个编写递归函数的合适案例。让我们展开以上定义以计算 5 的阶乘值。

It can be seen that we use factorial itself to define factorial. Hence this is a fit case to write a recursive function. Let us expand above definition for calculation of factorial value of 5.

5! = 5 × 4!
   5 × 4 × 3!
   5 × 4 × 3 × 2!
   5 × 4 × 3 × 2 × 1!
   5 × 4 × 3 × 2 × 1
= 120

虽然我们可以使用循环执行此计算，但其递归函数涉及通过递减数字依次调用它，直到数字变为 1。

While we can perform this calculation using a loop, its recursive function involves successively calling it by decrementing the number till it reaches 1.

以下示例显示了如何使用递归函数计算阶乘 -

The following example shows hows you can use a recursive function to calculate factorial −

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))

上述程序生成以下输出 −

The above programs generates the following output −

5 * 4 * 3 * 2 * 1
factorial of 5= 120

Recursive Case

递归情况是递归函数的一部分，其中函数自身调用自身来解决相同问题的更小或更简单的实例。此机制允许将复杂问题分解为更可管理的子问题，其中每个问题均为原始问题的较小版本。

The recursive case is the part of a recursive function where the function calls itself to solve a smaller or simpler instance of the same problem. This mechanism allows a complex problem to be broken down into more manageable sub-problems where each them is a smaller version of the original problem.

递归情况对于朝基本情况发展至关重要，确保递归最终会终止。

The recursive case is essential for progressing towards the base case, ensuring that the recursion will eventually terminate.

以下是递归情况的示例。在此示例中，我们生成 Fibonacci 数列，其中递归情况对前两个 Fibonacci 数的结果求和 −

Following is the example of the Recursive case. In this example we are generating the Fibonacci sequence in which the recursive case sums the results of the two preceding Fibonacci numbers −

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)

上述程序生成以下输出 −

The above programs generates the following output −

[0, 1, 1, 2, 3, 5]

Binary Search using Recursion

二分查找算法是一种用于快速查找已排序列表中的元素的强大算法，其采用对数时间复杂度，使其非常有效。

Binary search is a powerful algorithm for quickly finding elements in sorted lists, with logarithmic time complexity making it highly efficient.

让我们看另一个理解递归工作原理的示例。眼前的问题是检查给定数字是否存在于列表中。

Let us have a look at another example to understand how recursion works. The problem at hand is to check whether a given number is present in a list.

虽然我们可以使用 for 循环在列表中按顺序查找某个数字并比较每个数字，但如果列表太大，顺序查找效率不高。二分查找算法检查索引“high”是否大于索引“low”。根据“mid”变量中存在的 value，再次调用该函数来搜索元素。

While we can perform a sequential search for a certain number in the list using a for loop and comparing each number, the sequential search is not efficient especially if the list is too large. The binary search algorithm that checks if the index 'high' is greater than index 'low. Based on value present at 'mid' variable, the function is called again to search for the element.

我们有一个按升序排列的数字列表。然后我们找到列表的中间点，并根据所需的数字是否小于或大于中间点的数字来将检查限制在中间点的左右两侧。

We have a list of numbers, arranged in ascending order. The we find the midpoint of the list and restrict the checking to either left or right of midpoint depending on whether the desired number is less than or greater than the number at midpoint.

下图显示了二分查找的工作原理 -

The following diagram shows how binary search works −

python recursion

Example

以下代码实现了递归二分查找技术 -

The following code implements the recursive binary searching technique −

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!")

Output

The list is
[5, 12, 23, 45, 49, 67, 71, 77, 82]
Check for number: 67
Element found at index 5