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

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

您需要添加一个 "basis case"（递归停止的地方）。

这个问题的自然基础情况：如果start等于end，就returnA[start]

编辑：

我刚看了这个，越看越糊涂。为什么要使用递归来查找最大值？使用递归执行 "binary search" 以在排序列表中查找值会更有意义。

如果你真的想找到一个最大值，那很容易。对于递归，我们首先需要一个 "basis case" 来为我们提供一个简单的解决方案；那么我们需要更多代码，使我们离解决方案更近一步。

在这种情况下，基本情况：列表中只有一个值； return 它作为最大值。具体来说，如果start和end一起只指定一个值，return就是那个值。为了防止错误，不妨使它也处理 start 等于甚至大于 end.

的情况

接下来记住第一个值。

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

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

我会用伪代码为您列出：

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)

Answer 2

我同意 steveha 的大部分回答，但与其一次选择一个元素，我建议将列表分成两半并在每一半中找到最大值。您不会做任何更少的比较，但递归堆栈的增长将是 O(log(len(A))) 而不是 O(len(A))。对于大型列表，这将是堆栈溢出与否的区别。

我的实现（将列表作为参数而不是期望它是全局的）如下：

def recursive_max(value_list, start, end):
    if start >= end:
        return value_list[start]
    mid = start + (end - start) // 2
    lower_half_max = recursive_max(value_list, start, mid)
    upper_half_max = recursive_max(value_list, mid+1, end)
    if lower_half_max > upper_half_max:
        return lower_half_max
    else:
        return upper_half_max

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

recursion, finding max, why is it not stopping?

python

recursion