Python：递归函数查找列表中最大的数

Question

Python：递归函数查找列表中最大的数

5

我正在尝试完成《Zelle Python编程》教材中的一项实验任务。

问题要求我“编写并测试一个递归函数max()，以找到列表中的最大数字。最大值是第一项和所有其他项的最大值中更大的那个。”我不太理解教材中的问题。

def Max(list):
    if len(list) <= 1:
        else:
            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()

也许我应该打开一个带有数字的文本文件，然后使用递归？我认为递归的工作原理是这样的。

def function()
> if something:
>>return 0
>else:
>>return function()

- Jimmy Ly

什么是问题？不清楚。 - Damian Schenkelman

抱歉，这个问题来自教科书，所以我不知道如何更清楚地表达。 - Jimmy Ly

14个回答

7

我提供了一个不同的解决问题的方法。大多数答案在每次递归调用中使用切片运算符来操作列表。由于该练习没有提供严格的函数原型供使用，因此我还将列表长度作为函数参数传递。

假设我们试图从包含n个元素的序列S中找到并返回最大元素。

函数原型：Max(S, n)

基本情况：如果S只包含一个项目，则返回它。（显然，序列中唯一的项目是最大的。）

递归：如果不是基本情况，则每次调用Max时少一个项目，即调用Max(S, n-1)。然后，我们将返回值存储到一个名为previous的变量中，表示序列中的上一个元素，并将该值与序列中的下一个元素进行比较，即当前递归调用中的最右侧元素，并返回这些值中的最大值。

上述过程的递归跟踪如下图所示。假设我们试图从包含[5, 10, 20, 11, 3]的列表中找到最大值。

注意：为了帮助您更好地理解，我们会从列表的最右侧元素递归地迭代到最左侧元素。

最后，这是可工作的代码：

def find_max_recursively(S, n):                                                
    """Find the maximum element in a sequence S, of n elements."""             
    if n == 1:  # reached the left most item                                   
        return S[n-1]                                                          
    else:                                                                      
        previous = find_max_recursively(S, n-1)                                
        current = S[n-1]                                                       
        if previous > current:                                                 
            return previous                                                    
        else:                                                                  
            return current                                                     


if __name__ == '__main__':                                                     
    print(find_max_recursively([5, 10, 20, 11, 3], 5))

注意: 递归实现默认只能使用1000个最常见元素的序列。

为了防止无限递归，Python 的设计者故意决定限制同时激活的函数调用总数。这个限制的精确值取决于 Python 发行版，但典型的默认值是 1000。如果达到这个限制，Python 解释器会引发一个 RuntimeError 错误，并显示消息“超过最大递归深度”。

迈克尔·T·古德里奇（2013），Python 中的数据结构和算法, Wiley

要更改默认值，请执行以下操作：

import sys
sys.setrecursionlimit(1000000)

- georgegkas

很棒的文章，George。我想问一个额外的问题。我的代码如下：def large(x): if len(x) == 1: return x.pop(0) else: temp = x.pop(0) previous = large(x) if previous >= temp: return previous else: return temp; 它可以工作，但如果我使用 def large(x): if len(x) == 1: return x.pop(0) else: temp = x.pop(0) if large(x) >= temp: return large(x) else: return temp. 它会返回错误。你介意找出原因吗？谢谢。 - Qiang Super

3

这里有另一种解决上述问题的方法。

def maximum(L):
    if len(L) == 1:
        return L[0]
    else:
        return max(L[0],maximum(L[1:]))

所以以下是示例输入和输出：

L= [2,4,6,23,1,46]
print maximum(L)

生成

- Pramod Bhat

2

基本方法如下。

如果列表只包含一个元素，则该元素是最大值。立即返回它。
否则，列表包含多个元素。第一个元素可能是最大值，也可能不是。
第一个元素的最大值就是列表中的第一个元素。
对剩余部分（除第一个元素外的所有元素）递归调用Max，以找到这些元素的最大值。
比较步骤3和4的结果。结果是更大的数字。返回它。

现在你有一些语法错误。例如，你有两个else子句用于单个if，缩进看起来很奇怪。你只能为if块有一个else。但如果你遵循这些说明，你应该有一个工作的算法。

- recursive

1

这些解决方案在列表达到一定大小后会失败。

以下是更好的版本：

def maximum2(a, n):
    if n == 1:
        return a[0]
    x = maximum2(a[n//2:], n - n//2)
    return x if x > a[0] else a[0]
def maximum(a):
    return maximum2(a, len(a))

maximum(range(99999))


>>> 99998

- Daniel Fitzhenry

1

def find_max(my_list, max):
    if len(my_list) <= 1:
        return max
    else:
        if my_list[0] > max:
            return find_max(my_list[1:], my_list[0])
        else:
            return find_max(my_list[1:], max)

if __name__ == '__main__':
   my_list = [1, 5, 16, 9, 20, 40, 5]                                           
   print(find_max(my_list, my_list[0]))

- rbehravesh

请在您的答案中添加足够的细节，以便未来读者能够理解。 - Abhyuday Vaish

1

一种简单的方法是先对列表进行排序，然后使用索引。

这是一个可行的函数：

a = [1,233,12,34]

def find_max(a):
    return sorted(a)[-1]

- Hector Moreno-Bravo

但它没有使用递归。 - Sanaf

1

def Max(lis,maxx=-float("inf")):

    if len(lis) == 1:            #only one element in lis
        return maxx if maxx>lis[0] else lis[0]  #return lis[0] if it's greater than maxx

    else:
        m=lis[0] if lis[0]>maxx else maxx  # m = max(lis[0],maxx)
        return Max(lis[1:],m)              #call Max with lis[1:] and pass 'm' too

print Max([1,2,39,4,5,6,7,8]) #prints 39
print Max([1,2,3,4,5,6,7,8]) #prints 8

- Ashwini Chaudhary

0

def recursiveMax(a):
    if len(a) == 1:
        return a[0]
    else:
        return a[0] if a[0] > recursiveMax(a[1:]) else recursiveMax(a[1:])

测试：

print(recursiveMax([1, 2, 15, 6, 3, 2, 9]))
print(recursiveMax([98, 2, 1, 1, 1, 1, ]))

- franciscostacom

0

简而言之，当传递给函数的列表为空时，此代码也将起作用！

@jam的回答很棒。但是，我发现了一些条件问题，我认为@Blender在暗示这个问题。

当传递给函数的列表为空时，该代码将失败。有两种基本情况：

当列表为空时 -> 返回None
当列表只有一个项目时 -> 返回list[0]

然后是递归情况...将任何其他情况缩减为基本情况。

def recursive_max(arr):
    if len(arr) == 0:
        return None
    elif len(arr) == 1:
        return arr[0]
    else:
        maxItem = recursive_max(arr[1:])
        return maxItem if maxItem > arr[0] else arr[0]

- zsega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jam · Accepted Answer

你对递归的理解似乎没问题。

你的 if 块出了点问题，一个 if 后面跟了两个 else，而且缩进也不对。你需要删除第一个 else 并将 if 下面的所有代码向左缩进一级。例如：

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()