通过递归查找最大值的Python代码

Question

我对我的 Python 代码有疑问，该代码用于查找列表中的最大值。功能代码如下：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它将返回错误消息：<ipython-input-74-dd8676a7c4e6> in large(x)      3         return x.pop(0)      4     else:----> 5         temp = x.pop(0)      6         if large(x) >= temp:      7             return large(x)IndexError: pop from empty list玩具数据将是：inputlist = [6,1,3,2,3,4,5,6]large(inputlist)提前谢谢你的帮助。我找不到导致此错误的主要原因。至于我，这两个代码是完全相同的。

Answer 1

的问题

if large(x) >= temp:

    return large(x)

是你最终不止一次调用large(x)（因此pop），这是从列表中删除元素。

就个人而言，我更喜欢这种风格，而不是使用像pop.

def large(x):

    if len(x) == 1:

        return x[0]

    remainder = large(x[1:])

    return x[0] if x[0] > remainder else remainder

Answer 2

与 OneCricketeer 的解决方案相同，但无需在每次递归调用时都不必要地创建列表切片。它还处理一个空列表。

def large(x):

    def rec(y):

        try:

            v = next(y)

        except StopIteration:

            return None

        r = rec(y)

        if r is None:

           return v

        return v if v > r else r

    return rec(iter(x))

inputlist = [6,1,3,2,3,4,5,6]

print(large(inputlist))

print(large([]))

产生

6

None

Answer 3

因为这是一个递归练习，而不是我们在系统代码中做的事情，所以我会使用描述性代码而不是高效代码，并做类似的事情：

def largest(array):

    if array:

        head, *tail = array

        if tail and head < (result := largest(tail)):

            return result

        return head

    return None

if __name__ == "__main__":

    from random import choices

    array = choices(range(100), k=10)

    print(array, '->', largest(array))

输出

> python3 test.py

[46, 67, 0, 22, 23, 20, 30, 7, 87, 50] -> 87

> python3 test.py

[83, 77, 61, 53, 7, 65, 68, 43, 44, 47] -> 83

> python3 test.py

[36, 99, 47, 93, 60, 43, 56, 90, 53, 44] -> 99

> 

如果您真的需要提高效率，我建议您安全地这样做。具体来说，不公开带有调用者不应该使用的特殊参数的 API ，例如：

def my_max(lst, m=None, i=0):

因为他们可以为这些额外的参数提供值，这些参数会使您的代码失败，并最终将其归咎于您。同上公开调用者可能调用的内部函数而不是预期的函数：

def my_max(lst, m=None, i=0):

def my_max_helper(lst, i):

不小心调用了my_max_helper()命名不当的参数的虚假值i。相反，我会考虑嵌套您的函数以避免此类调用错误：

def largest(array):

    def largest_recursive(array, index):

        a = array[index]

        if len(array) - index != 1:

            if (b := largest_recursive(array, index + 1)) > a:

                return b

        return a

    if array:

        return largest_recursive(array, 0)

    return None

Answer 4

这并没有回答为什么原文不正确。相反，它制定了一个“标准模式”，可用于实现许多递归问题。

我想知道我应该如何用索引而不是弹出来消除每一轮中的元素数量？

不要“消除”元素 :-)

许多递归友好的问题通过缩小每一步的范围来运行。这包括寻找最大值（或任何可以表示为折叠的操作）、二分搜索、自上而下的归并排序等。其中许多问题本身都是使用数组和子问题减少的伪代码表示的通过调整每个递归调用的范围。在最大/二进制搜索的情况下，这也避免了对原始对象的任何突变。

因此，递归 max 函数可以写成如下形式。请注意，这种传递工作状态的形式是 Tail-Call Friendly。虽然我发现这种形式更容易表达某些问题，但它在 Python 中并不重要，因为[C]Python 不支持尾调用优化^{^}。

def my_max(lst, m=None, i=0):

  # base-case: return result of work

  if len(lst) == i:

    return m

  # Compute max through here

  c = lst[i]

  m = c if m is None or c > m else m

  # Call recursive function increasing the index by 1.

  # This is how the problem advances.

  return my_max(lst, m, i + 1)

上面的示例还使用默认参数而不是辅助方法。这是一个使用递归结果的替代方法——这通常是递归函数的引入方式——以及一个离散的辅助方法。

def my_max(lst):

  # Wrapper can ensure helper pre-conditions.

  # In this case that is a non-Empty list per the base case check.

  if not lst:

    return None

  return my_max_helper(lst, 0)

def my_max_helper(lst, i):

  # base case: last item in list returns itself

  if len(lst) - 1 == i:

    return lst[i]

  c = lst[i]

  m = my_max_helper(lst, i + 1)

  return c if c > m else m

在这两种情况下，都使用临时变量来避免重复表达式；虽然有时只是一种风格选择，但由于避免了额外弹出突变的意外副作用，这种一致性会减轻原始问题。

应list使用支持 O(1) 索引查找的a 或其他序列调用上述方法。特别是，“索引”方法不适合，也不会与生成器对象一起使用。还有其他的答案涵盖了这一点——只是要注意避免潜在的列表切片，比如h,*t=lor l[1:]，这可能会导致性能不佳。

^ Python 中有一些模块可以通过 spring-boarding模拟TCO。