Понимание Python рекурсии

Question

Я серьезно пытаюсь понять рекурсию Python. Нам поставили проблему, и я, по жизни, не могу ее понять.

Проблема: Напишите программу на python, которая печатает решение игрового поля, поставляемого в текстовой области. Числа в текстовой области создали игровое поле. Пример:

| 1 | 4 | 2 | 3 | 6 | 1 | 1 | 2 |

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

Обсуждение: Таким образом, из любой точки вы можете идти направо или налево. Итак, требования следующие: 1) Если индекс <0 ИЛИ индекс> длина доски - возвратная игра не может быть выиграна. 2) Если значение ячейки равно нулю, игра заканчивается, если она не является последней ячейкой на доске. 3) Каждая ячейка может быть толькопосетил один раз.

Что у меня есть:

def playGame(_currentIndex):
    _path.append(_currentIndex)
    print("Current Path --> ")
    print(_path)
    _currentIndex=_gameBoard[_currentIndex]
    win = False
    while win == False:
        #Check Can win from current position directly?
        if _currentIndex-1 or _currentIndex+1 == end:
            print("Game can be won directly from current position!")
            print(_path)
            return True
        #Check for Loss:
        #Index Too High or Too Low
        if _currentIndex < 0 or _currentIndex > end:
            print("Game cannot be won")
            exit(code = 0)
        #Cell Value of Zero
        elif _gameBoard[_currentIndex] == 0:
            #If Cell Value Zero and Is Last Cell
            if _currentIndex == end:
                print("Game won!")
                print(_path)
                win = True
            else:
                print("Game cannot be won")
                exit(code=0)
        #Cell has been visited before
        elif (_currentIndex in _path):
            print("Game cannot be won")
            exit(code = 0)
        elif (playGame(-(_currentIndex))) or (playGame(-(_currentIndex))):
            win = True
        else:
            win = False

Я получаю глубину рекурсии, превышенную при использовании игрового поля [1,1], и не могу понять, почему?

РЕДАКТИРОВАТЬ --- Итак, я понимаю рекурсию, если она выполняет только одну вещь, например:

def rec(int):
    if int == 0:
        return 0
    else:
        num = int + (int - 1)
        print(num)
        rec(int - 1)


rec(3)

Это прекрасно работает и печатает: 5 3 1

НоЧто делать, если я хотел сделать это путем сложения или вычитания до int == 0 или int == 10?

Answer 1

Ошибка глубины рекурсии возникает при отсутствии базового варианта для определенного состояния. Это часто является показательным признаком того, что вы либо не обрабатываете все базовые случаи, либо что ваш базовый случай не соответствует требованиям.

Я не могу сказать вам, в каком случае вы не снимаете, поскольку у меня нетданные игрового поля;однако это означает, что вы никогда не выходите из функции, что означает, что вы застряли в цикле while.

Answer 2

Учитывая заданную загадку ввода, q,

1. Если текущий индекс i выходит за границы или был замечен ранее в mem (базовый случай), вернуть False
2. В противном случае (индуктивный) i равен в границах и имеет не , замеченный ранее. Если i равно последнему индексу, вернуть решение, sln
3. В противном случае (индуктивное) i равно в границах, не быловидел, и не окончательный индекс. Добавьте i к mem и sln и рекурсивно попытайтесь найти i+q[i] или i-q[i]

Объяснение выше соответствует нумерованным комментариям ниже -

def solve(q, i = 0, mem = set(), sln = ()):
  if i in mem or i < 0 or i >= len(q):  #1
    return False
  elif i == len(q) - 1:                 #2
    return sln+(i,)
  else:                                 #3
    return \
      solve(q, i+q[i], mem|set([i]), sln+(i,)) \
    or \
      solve(q, i-q[i], mem|set([i]), sln+(i,))

puzzle = [1,4,2,3,6,1,1,2]

print(solve(puzzle))
# (0, 1, 5, 6, 7)

Ответом является последовательность индексов для достижения окончательного индекса -

 0 1 2 3 4 5 6 7     <-- index
[1,4,2,3,6,1,1,2]    <-- puzzle
 ^ ^       ^ ^ ^     <-- (0, 1, 5, 6, 7)

Необходимо использовать mem, чтобы избежать проверки одних и тех же индексов более одного раза. То есть, некоторые входные загадки могут привести к тому, что решатель попадет в бесконечный цикл. Если мы уже посещали индекс i один раз ранее, мы знаем, что это тупик, и поэтому мы возвращаем False

solve([3,0,1,1,1,0,3])
# False

В этом примере мы видим, что решение отскакивает, а затем, наконец, приземляется напоследний индекс -

solve([3,6,1,2,4,0,3,1,0,9])
# (0, 3, 1, 7, 6, 9)