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

标签： pythonpython-3.xrecursion

Answer 1

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

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

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哪个max([2])返回2。7更大，所以max([7,2])返回7。

  • 现在我们回到（2）。我们比较4and max([7,2])，我们已经看到返回7。既然7大了4，我们就回去7。

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

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