使用递归查找最大元素

Find max element using recursion

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

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 中查找最大元素的解决方案,但其中有找到最大元素位置的解决方案。提前致谢。

我认为任务只是找到最大数量 的 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

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

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

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

  • 基本情况应为 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 == 0high == 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 并在每个递归级别打印以查看它如何影响结果并获得全面的理解。