Сохранение значения переменной в рекурсивной функции, python 3.3

Question

Мне это удалось, каким-то другим способом. , но у меня есть вопрос, у меня был этот код перед

def jumphunt(start, mylist, count = 0): 
    if count < len(mylist): 
     place = mylist[start] 
     print(place) 
     if place == 0: 
      return True 
     elif start >= len(mylist) or start < 0: 
      return False 
     move_left = (start - place) 
     move_right = (start + place) 
     return jumphunt(move_right, mylist, count+1) or jumphunt(move_left, mylist, count+1) 
    else: 
     return False 

, но по какой-то причине он не пытается в обоих направлениях , чтобы добраться до последнего элемента в списке.

например: [1,2,2,3,4,5,3,2,1,7,0] и, start = mylist [0] он должен прыгать так (от 1-2 -4-1-left to 2-left to 5-right to 0) , но он продолжает пытаться идти вправо, а затем индекс за пределами допустимого диапазона и т. Д.

Я думал, что если вы используете возврат или тот или иной , он попытается до тех пор, пока не достигнет True, почему он не будет работать здесь?

Спасибо!

Answer 1

Включите значение, которое вы хотите сохранить в качестве параметра по умолчанию для метода, как это:

def my_func(int, list, i=0): 
    a = (i + int) 
    if int == 0: 
     return True 
    elif a > len(list): 
     i -= int 
    else: 
     i += int 
    int = list[i] 
    my_func(int, list, i) 

Имейте в виду, что это может даже не всегда можно прийти в конце списка делает который вы описываете, и даже если это возможно, этот метод может выбрать неправильную ветку.

Лучше алгоритм будет выглядеть следующим образом:

def branching_search(list, start): 
    marks = [0]*len(list) 
    pos = start 
    while list[pos]!=0: 
     marks[pos]++ 
     if marks[pos] % 2 == 0 and pos + list[pos] < len(list): 
      pos += list[pos] 
     elif marks[pos] % 2 == 1 and pos - list[pos] >= 0: 
      pos -= list[pos] 
     else: 
      return False 
     if all(item == 0 or item > 1 for item in list) 
      return False 
    return True 

Таким образом, если речь идет о предмете, что он уже побывал, он решил пойти в обратном направлении, что она пошла в последний раз. Кроме того, если дело доходит до предмета, который не может уйти, не выходя из-за пределов, или если нет способа добраться до конца, он сдастся и вернется.

EDIT: Я понял, что в этом алгоритме есть ряд недостатков! Хотя это лучше, чем первый подход, он не гарантированно работает, хотя причины несколько сложны.

Только представьте себе этот массив (несущественные элементы остаются пустыми):

1, 2, , 5, , , , , 5, 0 

Первые два элемента будет получить только один знак (таким образом, цикл проверки состояния не будет работать), но он все равно застрянет цикл между двумя пятью.

Вот метод, который будет работать всегда:

def flood_search(list): 

    marks = [[]]*len(list) 
    marks[0] = [0] 
    still_moving = True 

    while still_moving: 
     still_moving = False 

     for pos in range(0,len(list)): 
      if marks[pos]: 
       if pos + list[pos] < len(list) and not marks[pos + list[pos]]: 
        marks[pos + list[pos]] = marks[pos] + [list[pos]]; 
        pos += list[pos] 
        still_moving = True 

       if pos - list[pos] >= 0 and not marks[pos - list[pos]]: 
        marks[pos - list[pos]] = marks[pos] + [-list[pos]]; 
        pos -= list[pos] 
        still_moving = True 

    return marks[-1] 

Это работает, принимая каждый можно ветви одновременно.

Вы также можете использовать метод, чтобы получить фактический маршрут, пройденный, чтобы добраться до конца. Он все равно может использоваться как условие, так как он возвращает пустой список, если путь не найден (значение ложности) или список, содержащий путь, если найден путь (истинное значение).

Однако, вы всегда можете использовать list[-1], чтобы получить последний элемент.