Python递归函数与二分查找算法详解

一、初始递归

递归函数的定义是在函数内部调用函数自身。

递归的最大深度：998

如前文所述，若递归函数没有外部干预，它将无限执行。鉴于每次函数调用都会创建独立的名称空间，无限调用会导致内存占用激增。为此，Python强制将递归层数限制在997层（注：此处指最大深度数值为998，可用层数为997），以防止内存耗尽。

如何验证“998理论”？我们可以通过以下实验进行观察：

def foo(n):
  print(n)
  n += 1
  foo(n)
foo(1)

从实验结果可见，在未触发报错前，能显示的最大数字即为998。实际上，997是Python为优化程序内存而设定的默认值，但我们可以通过特定手段调整该限制：

import sys
print(sys.setrecursionlimit(100000))

通过上述方式可修改递归最大深度。例如，我们将Python允许的递归深度设置为10w，实际能达到的深度取决于计算机性能。尽管如此，通常不建议修改默认递归深度，因为若997层递归无法解决问题，通常意味着该问题不适合用递归解决，或代码实现存在缺陷。

此时，读者可能会认为递归并非最优选择，甚至不如while True循环直观。然而，业界有言：“人理解循环，神理解递归”。递归函数的重要性不容小觑，许多算法都基于递归原理。只有掌握递归，才能深入理解高级算法。

二、递归示例讲解

接下来，我们通过具体案例来说明递归的应用场景。

例一：

假设有人问Alex老师的年龄，我不直接回答，但告知Alex比Egon大两岁。

若想得知Alex年龄，需先询问Egon。Egon同样不直接回答，但表示他比武Sir大两岁。

接着询问武Sir，武Sir表示他比太白大两岁。

最后询问太白，太白告知自己18岁。

此时，你是否能推算出Alex的年龄？

你是如何得出这个结论的？

首先，你依次询问Alex、Egon、武Sir和太白，直到获得太白的确切年龄，然后沿原路径回溯计算，最终得出Alex的年龄。这一过程高度契合递归的核心思想。我们来具体分析这几个人物之间的规律。

age(4) = age(3) + 2 
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 40

基于此逻辑，我们的函数应如何编写？

def age(n):
  if n == 1:
    return 40
  else:
    return age(n-1)+2
print(age(4))

假设有一个列表，要求找出数字66在列表中的位置，该如何操作？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

你可能会觉得这很简单。

使用l.index(66)即可实现。

Python已内置查找方法。但如果不能使用index方法，你还能找到66吗？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
i = 0
for num in l:
  if num == 66:
    print(i)
  i+=1

上述代码展示了如何从列表中定位66的位置。

我们是通过遍历列表逐个比对来实现的。如果列表包含数十万个数字，且运气不佳，可能需要比对十几万次，效率极低。因此，我们需要寻找更高效的替代方案。

二分查找算法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

观察该列表，它是一个从小到大排序的有序列表。

基于此特性，若目标数大于列表中间值，则只需在列表的后半部分继续查找。

这就是二分查找算法的核心逻辑！

那么，如何用代码实现这一算法？

简单版二分法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def func(l,aim):
  mid = (len(l)-1)//2
  if l:
    if aim > l[mid]:
      func(l[mid+1:],aim)
    elif aim < l[mid]:
      func(l[:mid],aim)
    elif aim == l[mid]:
      print("bingo",mid)
  else:
    print('找不到')
func(l,66)
func(l,6)

升级版二分法

l1 = [1, 2, 4, 5, 7, 9]
def two_search(l,aim,start=0,end=None):
  end = len(l)-1 if end is None else end
  mid_index = (end - start) // 2 + start
  if end >= start:
    if aim > l[mid_index]:
      return two_search(l,aim,start=mid_index+1,end=end)
    elif aim < l[mid_index]:
      return two_search(l,aim,start=start,end=mid_index-1)

    elif aim == l[mid_index]:
      return mid_index
    else:
      return '没有此值'
  else:
    return '没有此值'
print(two_search(l1,9))

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。