递归列表遍历

Question

我需要遍历一个列表。列表的每个元素都是最大跳跃。所以如果我的起始位置是 5，那么我最多可以跳到列表中的 5 个位置。但是如果列表的第5个元素是0，那么它是一个无效的跳转，所以我必须将跳转减少1。我想递归地这样做，但它每次都重复相同的数字。

def traverse(lst,pos,out):
    out.append(pos)
    try:
        while lst[pos] + pos == 0:
            pos = pos - 1
        pos += lst[pos]
        traverse(lst,pos,out)       
    except IndexError:
        print(out[:-1] + ['out'])

c2 = [3,5,1,2,5,1,4]
traverse(c2,c2[0],out)

output: [3, 5,'out']

c3 =  [3,5,1,0,5,1,4] #So i changed the 3th value to 0
traverse(c3,c3[0],out)

output:
 3,
 3,
 3,
 3,
 ...]

直到最大递归错误。为什么我的pos不减值？

Answer 1

while 条件不正确：

while lst[pos] + pos == 0:

您确实要检查列表中的值：

while lst[lst[pos] + pos] == 0:

但是当你减少 pos 时，这仍然会留下一个问题：突然你会看到一个不同的 lst[pos]，而那确实应该保持不变。

所以，先增加pos然后循环会更有用：

pos += lst[pos]       # move this here, before the loop
while lst[pos] == 0:  # corrected condition
    pos = pos - 1

如评论中所述，这并不能防止算法卡住。如果您跳转到一个零值，而前一个值是 1，那么您将不断跳转到同一个零。

递归列表遍历

Recursive list traversal

python

arrays

recursion

traversal

list