Python - 递归

上一页
下一页

递归是程序设计中一个基本的概念，它指的是一个函数在函数体内调用自身。这种技术可以将一个复杂的问题分解成多个相同类型但规模更小的子问题。在 Python 中，递归是通过定义一个函数并在其函数体内调用自身来实现的。

递归的组成部分

正如我们之前讨论的，递归是一种函数调用自身的技巧。为了理解递归，我们需要了解其关键组成部分。以下是递归的主要组成部分：

  • 基本情况
  • 递归情况

基本情况

基本情况是递归中的一个基本概念，它充当递归函数停止调用自身的条件。它是防止无限递归和随之而来的堆栈溢出错误的关键。

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

递归最常见的例子是计算阶乘。从数学上讲，阶乘定义为：

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= 120

递归情况

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

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

示例

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

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]

使用递归进行二分查找

二分查找是一种强大的算法，可以快速在排序列表中查找元素，具有对数时间复杂度，使其效率极高。

让我们再看一个例子来了解递归是如何工作的。手头的问题是检查给定数字是否存在于列表中。

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

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

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

Python Recursion

示例

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

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

输出

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

上一页
下一页
广告