python - 递归，找到最大值，为什么不停止？

Question

我试图在排序列表中找到最大值。但递归并没有停止。请问有人可以帮助我吗？

A = [5,16,28,43,0,1]

start = 0
end = len(A) - 1
mid = 0

print mid

def search(start, end, mid):
  mid = int((start + end) / 2)
  print mid

  if A[mid] > [mid - 1] and A[mid] > A[mid + 1]:
    return A[mid]
  else:
    if A[mid - 1] > A[mid + 1]:
      search(start, mid, mid)
    else:
      search(mid, end, mid)

打印搜索(开始、结束、中间)

Answer 1

您需要添加一个“基本情况”(递归停止的地方)。

此问题的自然基本情况:如果 start 等于 end，则仅返回 A[start]

编辑:

我刚刚看了这个，我看得越多，我就越困惑。为什么要使用递归来找到最大值？使用递归进行“二分搜索”以在排序列表中查找值会更有意义。

如果你想真正找到最大值，那很容易。对于递归，我们首先需要一个“基本情况”来为我们提供一个简单的解决方案；然后我们需要更多代码来让我们更接近该解决方案。

在这种情况下，基本情况是:列表中只有一个值；返回它作为最大值。具体来说，如果 start 和 end 一起仅指定一个值，则返回该值。为了防止错误，不妨让它也处理 start 等于甚至大于 end 的情况。

接下来记住第一个值。

接下来进行递归调用，但在 start 中添加一个以减少我们正在考虑的列表的大小。这是让我们更接近解决方案的部分。重复此步骤足够多次，我们就会得到基本情况，其中列表中只有一个值需要考虑。

最后将记住的第一个值与递归调用的结果进行比较，并返回两者中较大的一个。

我会用伪代码为您展示它:

BASIS CASE: start and end specify one value: return A[start]
save A[0] in a variable
save recursive_call_to_this_function(start+1, end) in a variable
compare two saved values and return the larger

一旦您尝试在代码中编写上述内容，请查看此行下面的我的工作测试解决方案。

def recursive_max(start, end):
    if start >= end - 1:
        return A[start]
    x0 = A[start]
    x1 = recursive_max(start+1, end)
    if x0 >= x1:
        return x0
    else:
        return x1

print recursive_max(start, end)