Рекурсивный обход списка - PullRequest
Новая
       11

Рекурсивный обход списка

0 голосов
/ 12 марта 2019

Мне нужно пройти список.Каждый элемент списка является максимальным прыжком.Поэтому, если моя стартовая позиция 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,
 ...]

До максимальной рекурсивной ошибки.Почему мой пост не уменьшает значение?

1 Ответ

1 голос
/ 12 марта 2019

Условие 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, то вы будете снова и снова переходить к этому же нулю.

...