使用递归查找最大元素

Question

我是递归的新手，任务是使用递归找到数组中最大元素的位置。这是我的代码：

def calc(low , high):
    print(low, high)
    if low == high:
        return low
    max_1 = calc(low , low +high//2)
    max_2 = calc(low + high//2 , high)
    if a[max_1] > a[max_2]:
        return max_1
        
a = [4,3,6,1,9]
print(calc(0 , len(a)))

我做错了什么？虽然 google 为我提供了在数组 none 中查找最大元素的解决方案，但其中有找到最大元素位置的解决方案。提前致谢。

Answer 1

我认为任务只是找到最大数量的 POSITION（而不是值本身）。

因此，函数首先将最后一个值与列表的最大值进行比较，如果为真，则returns列表的长度（减一）作为位置。然后它被递归地调用到一个较短的列表并再次比较，直到它在列表中只剩下一个值

def calc(lst): if lst[len(lst) - 1] == max(lst): return len(lst) - 1 if len(lst) > 1: return calc(lst[:-1]) print(calc([0, 1, 2, 3, 4, 5, 6])) # 6 print(calc([7, 1, 2, 3, 4, 5, 6])) # 0 print(calc([0, 1, 8, 3, 4, 5, 6])) # 2

Answer 2

我想这就是你想要做的。您应该将列表切片传递给函数 - 这比尝试传递低索引和高索引要简单得多，并且避免将列表作为全局变量访问 - 并将中点添加到来自右侧的结果索引列表。

def idxmax(l):
    if len(l) == 1:
        return 0
    midpoint = len(l) // 2
    a = idxmax(l[:midpoint])
    b = idxmax(l[midpoint:]) + midpoint
    if l[a] >= l[b]:
        return a
    else:
        return b

print(idxmax([4,3,6,1,9]))

此returns 第一个 出现最大值的索引，例如idxmax([4,9,3,6,1,9]) == 1

如果你想通过传递索引而不是切片来实现它（通过不制作列表的多个副本可能更有效），你可以这样做：

def idxmax(l, start=0, end=None):
    if end is None:
        end = len(l) - 1
    if end == start:
        return start
    midpoint = (start + end) // 2
    a = idxmax(l, start, midpoint)
    b = idxmax(l, midpoint + 1, end)
    if l[a] >= l[b]:
        return a
    else:
        return b

print(idxmax([4,3,6,1,9]))

Answer 3

你快到了。两个小错误是：

基本情况应为 low + 1 == high
中点应该是 (low + high) // 2

def calc(low , high):
    if low + 1 == high:
        return low 
    max_1 = calc(low , (low + high) // 2)
    max_2 = calc((low + high) // 2 , high)
    if a[max_1] > a[max_2]:
        return max_1
    else:
        return max_2
        
a = [4,3,6,1,9]

print(calc(0 , len(a)))
## 4

由于错误的基本情况和 mid-point.

，您的解决方案会生成无限递归

当low == 0和high == 1时，因为low != high你触发了两次调用

max_1 = calc(low , low + high // 2) 
max_2 = calc(low + high // 2 , high)

评估为

max_1 = calc(0, 0) ## This got returned to 0, because low == high
max_2 = calc(0, 1) ## Notice here again low == 0 and high == 1

第二个调用 max_2 = calc(0, 1) 再次触发另外两个调用，其中一个又是 max_2 = calc(0, 1)。这会触发无限递归，永远不会 returns 回到 max_2 并且 max_2 永远不会被评估，因此它后面的行 (if a[max_1] > a[max_2]: ... ).

这就是为什么您应该检查基本情况 low + 1 == high 而不是 low == high。现在您可以测试自己并猜测以下代码是否会生成无限递归。这次 max_2 会得到分配给它的返回值以及它被评估后的行吗？

def calc(low , high):
    if low + 1 == high: # Here is changed from your solution
        return low 
    max_1 = calc(low , low + high // 2) # Here is same to your solution
    max_2 = calc(low + high // 2 , high) # Here is same as well
    if a[max_1] > a[max_2]:
        return max_1
    else:
        return max_2

如果您答对了，那么您就已经了解了错误的一半。然后你可以尝试不同的 mid-point 并在每个递归级别打印以查看它如何影响结果并获得全面的理解。

使用递归查找最大元素

Find max element using recursion

python

python-3.x

recursion

max