理解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 三 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)