python - 递归如何找到最大值？

Question

有人可以解释一下 restMax = max(A[1:]) 行如何找到数组中的最大元素吗？我知道它每次都会将其分解为子数组，但是如何找到最大值？

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)，则不会返回任何内容。

if len(A)==0 :
    return None

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

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

如果在包含多个元素的数组上调用 max(A)，则会执行以下操作:

• 它将 A 分成两个:第一个元素(头，A[0])和其他元素(尾，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 和返回 2 的 max([2])。 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 和 7。 7 更大，因此 max([1,4,7,2]) 返回 7。

我们完成了! max([1,4,7,2]) 为 7。