4

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

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

或者,也许我想打开一个带有数字的 txt 文件,然后使用递归?

我相信这样的递归作品

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

12 回答 12

15

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

你的 if 块搞砸了,你有 2else对 1if并且对齐不正确。您需要删除一个级别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()
于 2012-10-03T15:12:37.100 回答
5

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

假设我们尝试从包含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带有消息的 a maximum recursion depth exceeded

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

要更改默认值,请执行以下操作:

import sys
sys.setrecursionlimit(1000000)
于 2017-05-19T20:05:53.843 回答
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)

生产

46
于 2013-12-12T17:28:07.930 回答
2

基本方法是这样的。

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

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

于 2012-10-03T15:15:25.727 回答
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   
于 2012-10-03T15:14:54.370 回答
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
于 2014-11-22T20:26:57.423 回答
0

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

这是一个可行的功能:

a = [1,233,12,34]

def find_max(a):
    return sorted(a)[-1]
于 2018-11-16T11:32:09.973 回答
0
def find_max(arr):
  """find maximum number in array by recursion"""
  if arr == []: # if its an empty array
    return 0
  if len(arr) == 1: # if array has only one element
    return arr[0]
  else: # get max of first item compared to other items recursively
    return max(arr[0], find_max(arr[1:])) # 1: means all other excluding 0th element

def main():
  print(find_max([2,3,5,6,7,1])) # will print max - 7

if __name__ == "__main__":
  main()
于 2020-07-21T11:57:36.413 回答
0

你也可以这样做:

def maximum(data, start, stop):

    if start >= stop:
            return data[start]

    else:
            if data[start] >= data[stop - 1]:
                return maximum(data, start, stop - 1)

            else:
                return maximum(data, start + 1, stop)
于 2021-01-03T19:28:52.077 回答
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, ]))
于 2021-02-21T05:10:32.520 回答
-1

这是我的答案,只有一行代码:))

def max_value(n_list):
    return n_list[0] if len(n_list) == 1 else max(n_list[0], max_value(n_list[1:]))
于 2020-10-02T07:50:01.407 回答
-3
def getMaxNumber(numbers): 
    return 'N.A' if len(numbers) == 0 else max(numbers)
于 2016-01-31T04:12:48.600 回答