I need to traverse a list. Each element of the list is the maximum jump. So if my starter position is 5, then i can jump maximum 5 positon in the list. But if the 5th element of the list is 0, then it's an invalid jump, so i have to reduce the jump by 1. I want to do this recursively, but it keep repeating the same number every time.
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,
...]
Until maximum recursive error. Why isnt my pos reducing the value?
The while condition does not do the right thing:
while lst[pos] + pos == 0:
You really want to check the value in the list:
while lst[lst[pos] + pos] == 0:
But that still leaves a problem when you decrease pos: suddenly you will be looking at a different lst[pos], while that really should stay fixed.
So, it will be more useful to first increase the pos and then do the loop:
pos += lst[pos] # move this here, before the loop
while lst[pos] == 0: # corrected condition
pos = pos - 1
As noted in comments, this does not prevent the algorithm to get stuck. If you jump to a value that is zero, and the preceding value is a 1, then you'll keep jumping into that same zero over and over again.