使用递归函数查找最大元素

Question

我写了一个函数,试图找出列表中具有最大值的内容:

def maxElement(L):
    length=len(L)
    if L[length-1]>L[length-2]:
        del L[length-2]
        print L
    elif L[length-1]<L[length-2]:
        del L[length-1]
    return L

print maxElement([1,2,95754754745,3,1,8,444,2,42425])

我的输出错了:

>>> 
[1, 2, 95754754745L, 3, 1, 8, 444, 42425]
[1, 2, 95754754745L, 3, 1, 8, 444, 42425]
>>> 

它甚至不会删除我所要求的内容.我做错了什么？我无法得到它!

Answer 1

你没有再次调用你的函数,这使得递归变得不可能.此外,你没有基本情况会停止递归,在这种情况下将是:

if length == 1:
  return L

这是固定代码:

def maxElement(L):
    length=len(L)
    if length == 1:
        return L
    elif L[length-1]>=L[length-2]:
        del L[length-2]
    elif L[length-1]<=L[length-2]:
        del L[length-1] 
    return maxElement(L)    

print maxElement([1,2,95754754745,3,1,8,444,2,42425])

这输出:

python recursive.py
 > [95754754745L]

我还添加<=并>=在条件语句以避免无限递归如果有共享的最大值两个元素.

Answer 2

它完全按照你的要求去做.

你的功能不是递归的,因为你忘了再次调用它.

这样的东西就是你要找的东西:

def maxElement(L):
    length=len(L)
    if L[length-1]>L[length-2]:
        del L[length-2]
        print L
    elif L[length-1]<L[length-2]:
        del L[length-1]
    if len(L) == 1:
        return L
    return maxElement(L)

print maxElement([1,2,95754754745,3,1,8,444,2,42425])

这将返回:

[1, 2, 95754754745L, 3, 1, 8, 444, 42425]
[1, 2, 95754754745L, 3, 1, 8, 42425]
[1, 2, 95754754745L, 3, 1, 42425]
[1, 2, 95754754745L, 3, 42425]
[1, 2, 95754754745L, 42425]
[1, 95754754745L]
[95754754745L]
[95754754745L]

我会更好一点,如下:

def maxElement(L):
    length=len(L)

    if length == 1:
        # Have this condition on the top because you are using length - 2 later
        # Just return the only element

        return L

    if L[length-1] > L[length-2]:
        # If the last element is greater than the last but one, delete the last but one
        del L[length - 2]

    else:
        # Simple else would suffice because you are just checking for the opposite
        # Also this condition saves you from:
        #       infinite looping when the last two elements are equal
        del L[length - 1]

    print L

    # Time to call it recursively.
    # But if you just don't want to unnecessarily increase the recursion
    # tree depth, check for length and return it

    if length == 1:
        return L
    return maxElement(L)