python - 递归在python代码中工作以找到最大值

Question

我是递归概念的新手，想弄清楚下面的代码是如何工作的

def Max(list):
    if len(list) == 1:
        return list[0]
    else:
        m = Max(list[1:])
        return m if m > list[0] else list[0]

def main():
    list = eval(raw_input(" please enter a list of numbers: "))
    print("the largest number is: ", Max(list))


    main()

看代码有以下疑惑

1) 切片在这里是如何工作的，而没有给出切片应该结束的位置 [0:9](以这种方式如何对列表进行切片)

2) **return m if m > list[0] else list[0]** 语句何时会被调用(我认为它不会被调用，因为在 return 之前我们将调用函数几个次)

Answer 1

欢迎来到递归——它很难理解，但它有一种奇怪的优雅/美丽。

它通常可以通过一个例子来帮助我思考这个问题。

让我们假设这个列表:1, 2, 3

我们要运行 Max([1,2,3])

1. 列表的长度是3，所以我们跳转到else部分
2. 我们运行 Max([2,3]) 并将结果保存到 m(递归 #1)
   1. [2,3]的长度为!= 0，我们去else
   2. 我们运行 Max([3]) 并将结果保存到 m(递归 #2)
      1. [3]的长度为== 1
      2. 我们返回索引 0，即 3(递归 #2 结束)
   3. 我们得到 3 的值 m
   4. 现在我们得到语句return m if m > list[0] else list[0]
   5. 回顾:m = 3 和 list=[2,3]
   6. m > list[0] 所以我们返回 m=3(递归结束 #1)
3. 再次回顾时间:m=3 和 list=[1,2,3]
4. m > list[0] 所以我们返回 m=3

Max([1,2,3]) 的结果是 3。

请注意，代码中对 Max 的每次调用都会为 m 和 list 创建"new" 变量仅在该函数内部可见。内部 Max 不知道外部 Max 的 m 和 list ，反之亦然。

调用流程如下所示:

+----------------+
|   Max([1,2,3]  | +----+
+------^---------+      | Step 1
       |                |
Step 4 |       +--------v------+
       +-------+   Max([2,3])  +---+
   return 3    +---^-----------+   | Step 2
                   |               |
           Step 3  |     +---------v-----+
                   +-----+   Max([3])    |
             return 3    +---------------+

地址 1):

当我们使用 [n:] 切片时，这意味着:从索引 n 开始并获取列表的其余部分。

地址 2):

在我们退出递归之后，请看上面的例子。

---

延伸阅读

• Analogy for teaching recursion关于 CS 教育 worker

---

根据您的评论进行编辑

为了帮助您理解 return m if m > list[0] else list[0] 这行我建议您尝试在头脑中跟踪递归调用之前和递归调用之后的状态.

这个 Max 实现的想法是这样的:递归地转到列表中的最后一个元素，然后将它与倒数第二个元素进行比较，如果最后一个更大，则保留那个，否则保留倒数第二个。

如果您的列表看起来像这样 [1,6,3,5,4,2]，则递归级别将返回:

括号中的第一个数字是m，第二个是list[0]的值

• 2(不适用，2)
• 4 (2, 4)
• 5 (4, 5)
• 5 (5, 3)
• 6 (5, 6)
• 6 (6, 1)

最终函数从列表的末尾开始，将最后一个值作为初始值并移动到开头，同时始终保持较大的值，从而返回最大值。

(这很难写出来，希望你能理解)