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

Python: Recursive function to find the largest number in the list

提问by Jimmy Ly

I'm trying to do a lab work from the textbook Zelle Python Programming

我正在尝试根据教科书 Zelle Python Programming 进行实验室工作

The question asked me to "write and test a recursive function max()to find the largest number in a list. The max is the larger of the first item and the max of all the other items." I don't quite understand the question from the textbook.

该问题要求我“编写并测试一个递归函数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()

Or maybe I'm suppose to open a txt file with numbers in it and then use recursive?

或者我想打开一个带有数字的txt文件，然后使用递归？

I believe recursive works like this

我相信递归是这样的

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

采纳答案by jam

Your understanding of how recursion works seems fine.

您对递归如何工作的理解似乎很好。

Your if-block is messed up, you have two elses to one ifand the alignment is out. You need to remove your first elseand un-indent everything below the ifone level. eg:

您的 if 块搞砸了，您有两个elses 和一个if对齐方式。您需要删除第一个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()

回答by Ashwini Chaudhary

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   

回答by recursive

The basic approach is this.

基本方法是这样的。

1. If the list contains only a single element, that element is the max. Return it immediately.
2. Otherwise, the list contains multiple elements. Either the first element in the list is the maximum, or it is not.
3. The maximum of the first element is simply the first element in the list.
4. Recursively call Maxon the rest (all but first element) to find the maximum of those elements.
5. Compare the results from step 3 and 4. The result is the number that is greater. Return it.

1. 如果列表仅包含单个元素，则该元素是最大值。立即归还。
2. 否则，列表包含多个元素。列表中的第一个元素要么是最大值，要么不是。
3. 第一个元素的最大值只是列表中的第一个元素。
4. 递归调用Max其余元素（除第一个元素外的所有元素）以找到这些元素的最大值。
5. 比较步骤 3 和 4 的结果。结果是较大的数字。把它返还。

Right now you have some syntax errors. For example, you have two elseclauses for a single if, and the indentation looks funny. You can only have one elsefor an ifblock. But if you follow these instructions, you should have a working algorithm.

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

回答by Pramod Bhat

here is one more approach to solve above problem

这是解决上述问题的另一种方法

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

so example input and output:

所以示例输入和输出：

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

produces

产生

46

回答by Daniel Fitzhenry

These solutions fail after certain list size.

这些解决方案在特定列表大小后失败。

This is a better version:

这是一个更好的版本：

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

回答by Palaxayya. Hiremath

def getMaxNumber(numbers): 
    return 'N.A' if len(numbers) == 0 else max(numbers)

回答by George Gkasdrogkas

I post a different solution approach of the problem. Most of the answers manipulate the list using the slice operator in each recursive call. By the time the exercise does not provide a strict function prototype to be used, I also pass as function parameter the length of the list.

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

Suppose that we try to find and return the maximum element from a sequence S, of nelements.

假设我们试图找到并从序列返回的最大元素小号的，ñ元素。

Function prototype:Max(S, n)

函数原型：Max(S, n)

Base case:If Scontains only one item, return it. (Obviously the only item in the sequence is the max one.)

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

Recur:If not the base case, call Maxeach time for one less item, that is call Max(S, n-1). We then store the returning value to a variable called previousthat indicate the previous element from the sequence and check that value with the next element in the sequence, which is the right most element in the current recursive call, and return the max of these values.

重复：如果不是基本情况，则Max每次调用少一个项目，即 call Max(S, n-1)。然后，我们将返回值存储到一个名为的变量中，该变量previous指示序列中的前一个元素，并使用序列中的下一个元素（即当前递归调用中最右边的元素）检查该值，并返回这些值的最大值。

A recursion trace of the above procedure is given in the following figure. Suppose we try to find the max from a list that contains [5, 10, 20, 11, 3].

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

Note:To help you further, keep in mind that we recursively iterate the list from the right most element to the left most one.

注意：为了进一步帮助您，请记住我们从最右边的元素到最左边的元素递归地迭代列表。

Finally here is the working code:

最后是工作代码：

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

Note:The recursive implementation will work by default only with sequences of 1000 most elements.

注意：默认情况下，递归实现仅适用于最多 1000 个元素的序列。

To combat against infinite recursions, the designers of Python made an intentional decision to limit the overall number of function activations that can be simultaneously active. The precise value of this limit depends upon the Python distribution, but a typical default value is 1000. If this limit is reached, the Python interpreter raises a RuntimeErrorwith a message, maximum recursion depth exceeded.

Michael T. Goodrich (2013), Data Structures and Algorithms in Python, Wiley

为了对抗无限递归，Python 的设计者有意决定限制可以同时激活的函数激活的总数。此限制的精确值取决于 Python 分布，但典型的默认值为1000. 如果达到此限制，Python 解释器将引发RuntimeError带有消息maximum recursion depth exceeded.

Michael T. Goodrich (2013)，Python 中的数据结构和算法，Wiley

To change the default value do:

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

import sys
sys.setrecursionlimit(1000000)

回答by Hector Moreno-Bravo

One simple way would be to sort the list first then use indexing.

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

Here's a function that would work:

这是一个可以工作的函数：

a = [1,233,12,34]

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