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。

示例1

以下示例展示了如何使用递归函数来计算阶乘：

def factorial(n):

   if n == 1:
      print (n)
      return 1
   else:
      print (n,'*', end=' ')
      return n * factorial(n-1)

print ('factorial of 5=', factorial(5))

它将产生以下 输出 −

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

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

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

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

下面的图示展示了二分搜索的工作原理 –

示例2

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

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

您可以检查列表中的不同数字的输出，以及不在列表中的数字。