递归如何找到最大值？

Question

有人能解释一下restMax = max(A[1:])行如何在数组中找到max元素吗？我知道它每次都会分解成子阵列，但这是如何找到最大值的呢

def max(A):
     if len(A)==0 :
        return None
     if len(A)==1 :
        return A[0]
     restMax = max(A[1:])
     if A[0]>restMax :
        return A[0]
     return restMax

Answer 1

递归函数一开始可能很棘手，所以让我们来看看这个函数的作用：

如果对空数组调用max(A)，则返回none

if len(A)==0 :
    return None

如果对具有单个元素的数组调用max(A)，它将返回该元素：

if len(A)==1 :
    return A[0]

如果对包含多个元素的数组调用max(A)，它将执行以下操作：

• 它将A分成两部分：第一个元素（head，A[0]）和其他元素（tail，A[1:]）
• 它递归地找出尾部的最大值（max(A[1:])，棘手的部分）
• 如果头部大于尾部的最大值，则返回头部。否则它将返回尾部的最大值

总而言之：

让我们看一下max([1,4,7,2])的样子：

• （1）[1,4,7,2]有几个元素，所以我们把它分成两部分：1和[4,7,2]。让我们看看max([4,7,2])是什么：

  • （2）[4,7,2]分为4和[7,2]。让我们看看max([7,2])是什么

    • （3）[7, 2]分为7和[2]。让我们看看max([2])是什么

      • （4） [2]有一个元素，因此max([2])返回2

    • 现在我们回到（3）。我们比较返回{}的{}和{}7更大，因此max([7,2])返回7

  • 现在我们回到（2）。我们比较了4和max([7,2])，我们已经看到它们返回了7。因为7比4大，所以我们返回7

• 现在我们回到（1）。我们已将原始数组拆分为1和[4,7,2]max([4,7,2])返回了7，因此我们比较了1和77更大，因此max([1,4,7,2])返回7

我们完了max([1,4,7,2])是7