Python - 递归

---

调用自身的函数称为递归函数。当某个问题本身被定义时，使用此方法。尽管这涉及迭代，但使用迭代方法来解决此类问题可能会很乏味。递归方法为看似复杂的问题提供了非常简洁的解决方案。

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

n! = n × (n-1)!

可以看出，我们使用factorial本身来定义阶乘。因此，这是编写递归函数的合适情况。让我们扩展上面的定义来计算 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

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