Python递归深度超出限制，不知道如何删除递归

Question

也许可以通过删除那些函数来解决问题，是吧？不过，我真的不知道该怎么做才能让源代码正常运行。顺便说一下，它只是模拟了一匹马在棋盘上转来转去，随机地尝试访问每个方格一次；但是我遇到了递归深度超出限制的错误。

import random

def main():
    global tries,moves
    tries,moves=0,0
    restart()

def restart():
    global a,indexes,x,y
    a=[[0 for y in range(8)] for x in range(8)] #Costrutto chic
    indexes=[x for x in range(8)]
    #Random part
    x=random.randint(0,7)
    y=random.randint(0,7)
    a[x][y]=1
    start()

def start():
    global i,indexes,moves,tries
    i=0
    random.shuffle(indexes) #List filled with random numbers that i'll use as indexes
    while i<=7:
        if indexes[i]==0:
            move(-2,-1)
        elif indexes[i]==1:
            move(-2,1)
        elif indexes[i]==2:
            move(-1,-2)
        elif indexes[i]==3:
            move(-1,2)
        elif indexes[i]==4:
            move(1,-2)
        elif indexes[i]==5:
            move(1,2)
        elif indexes[i]==6:
            move(2,-1)
        elif indexes[i]==7:
            move(2,1)
        i+=1
    for _ in a:
        if 0 in _:
            print "Wasted moves: %d"%(moves)
            tries+=1
            moves=0
            restart()
    print "Success obtained in %d tries"%(tries)

def move(column,row):
    global x,y,a,moves
    try: b=a[x+row][y+column]
    except IndexError: return 0
    if b==0 and 0<=x+row<=7 and 0<=y+column<=7:
        x=x+row
        y=y+column
        a[x][y]=1
        moves+=1
        start()
    else: return 0

try :main()
#except: print "I couldn't handle it" <-Row added to prevent python from returning a huge amount of errors

编辑：这是修改后的版本，虽然仍然不行，但至少有所改进：

import random

def move((column,row),x,y):
    try: cell=squares_visited[x+row][y+column]
    except IndexError: return x,y ## NONE TYPE OBJECT
    if cell==0 and 0<=x+row<=7 and 0<=y+column<=7:
        x+=row
        y+=column
        squares_visited[x][y]=1
        return x,y ## NONE TYPE OBJECT

squares_visited=[[0] * 8 for _ in range(8)]
x=random.randint(0,7)
y=random.randint(0,7)
squares_visited[x][y]=1
moves=[(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]
indexes=list(range(8))
tries=0
print "The horse starts in position %d,%d"%(x,y)

while True:
    random.shuffle(indexes)
    for _ in indexes:
        cells=move(moves[indexes[_]],x,y) ##Passing as arguments x and y looks weird
        x=cells[0]
        y=cells[1]
    #If you out this for cicle, there are no legal moves anymore(due to full completion with 1, or to lack of legit moves)
    for _ in squares_visited:
        if 0 in _:
            squares_visited=[[0] * 8 for _ in range(8)]
            tries+=1
    else:
        print "You managed to do it in %d tries."%(tries)

Answer 1

start() 和 move() 互相调用，这种情况叫做间接递归调用，但 move() 的 return 语句是从 move() 中返回，而不是从递归中返回。

你看，当你调用一个函数，它又调用另一个函数，然后那个函数又调用其他函数，这些调用会形成一个堆栈，每个调用都会被记录在里面。当你得到最终结果时，应该是从最后一个调用开始逐步返回，逐一解除这些函数调用。

在这里，你并没有这样做，你调用了 move()，它又调用了 start()，然后返回了某个值，但你却继续在堆栈中深入。

试着把你的代码改成迭代的版本。递归比较复杂，先从简单的开始。

如果你真的想坚持使用递归版本，可以让 move() 自己调用自己，然后在达到结束条件后，从它自己开始逐步返回。这样会比两个函数之间的递归调用更清晰。

顺便说一下：

• 尽量避免使用全局变量。要么把数据作为参数传递，要么使用类。我建议使用参数传递，这样会迫使你想出比现在更好的算法。
• while 循环不是必须的，可以用索引的 for 循环来替代。
• 那个庞大的 if/elif 语句也不必要，可以用字典来替代。

最后你应该得到类似这样的结果：

for i in indexes:
    move(*MOVES[i])

MOVES 是一个字典，里面存储了与 move() 参数相关的 i 的值。

• 你可能想用生成器来替代列表推导式，但这需要一些算法上的调整。这样可能会更节省内存。至少，要把这段代码写得更简洁：

[x for x in range(8)] 可以简化为 range(8)，[[0 for y in range(8)] for x in range(8)] 可以简化为 [[0] * 8 for x in range(8)]

range() 可以用 xrange() 来替代。

Answer 2

这段代码有很多问题，值得我们逐一分析：

import random

def main():
    global tries,moves

首先，这里有很多全局变量的过度使用。尽量传递参数，或者创建一个类。这是一种通用的策略，可以帮助你写出更易懂（也更容易调试）的算法。总的来说，这也是你代码失败的原因之一——不是因为某个特定的错误，而是因为代码的复杂性让你很难找到错误。

    tries,moves=0,0
    restart()

def restart():
    global a,indexes,x,y

你为什么把棋盘命名为a？这个名字太糟糕了！用一些更能描述的名字，比如squares_visited。

    a=[[0 for y in range(8)] for x in range(8)] #Costrutto chic
    indexes=[x for x in range(8)]

小问题：在Python 2中，[x for x in range(8)] == range(8)——它们的作用完全相同，所以列表推导式是多余的。在Python 3中，情况稍有不同，但如果你想要一个列表（而不是range对象），只需用list来转换，比如list(range(8))。

    #Random part
    x=random.randint(0,7)
    y=random.randint(0,7)
    a[x][y]=1
    start()

到目前为止，我对代码的理解是a是棋盘，x和y是起始坐标，你用1标记了第一个访问过的位置。到这里还不错。但是接下来就变得复杂了，因为你在restart的末尾调用了start，而不是从一个顶层控制函数调用它。这在理论上是可以的，但让递归变得比必要的更复杂；这也是你问题的一部分。

def start():
    global i,indexes,moves,tries

唉，又是全局变量……

    i=0
    random.shuffle(indexes) #List filled with random numbers that i'll use as indexes
    while i<=7:
        if indexes[i]==0:
            move(-2,-1)
        elif indexes[i]==1:
            move(-2,1)
        elif indexes[i]==2:
            move(-1,-2)
        elif indexes[i]==3:
            move(-1,2)
        elif indexes[i]==4:
            move(1,-2)
        elif indexes[i]==5:
            move(1,2)
        elif indexes[i]==6:
            move(2,-1)
        elif indexes[i]==7:
            move(2,1)
        i+=1

好吧，你想做的是依次遍历indexes中的每个索引。可是你为什么要用while呢？而且i为什么是全局的？我没看到它在其他地方被使用。这太复杂了。直接用for循环遍历indexes就可以了，像这样：

    for index in indexes: 
        if index==0:
            ...

好了，现在来看具体的问题……

    for _ in a:
        if 0 in _:
            print "Wasted moves: %d"%(moves)
            tries+=1
            moves=0
            restart()
    print "Success obtained in %d tries"%(tries)

我不太明白你在这里想做什么。看起来你每次在棋盘上找到0（即未访问的位置）时就调用restart。但是restart会把所有棋盘的值重置为0，所以除非你在到达这个点之前有其他方法把棋盘填满1，否则这会导致无限递归。实际上，move和start之间的相互递归原则上可能实现这一点，但就目前而言，复杂得太多了！问题在于没有明确的递归终止条件。

def move(column,row):
    global x,y,a,moves
    try: b=a[x+row][y+column]
    except IndexError: return 0
    if b==0 and 0<=x+row<=7 and 0<=y+column<=7:
        x=x+row
        y=y+column
        a[x][y]=1
        moves+=1
        start()
    else: return 0

在这里，原则上，如果你的移动碰到1或者超出棋盘范围，那么当前的递归分支就会终止。但是因为i和indexes在start中是全局的，当start被重新调用时，它会重新洗牌indexes并把i重置为0！结果就是一片混乱！我甚至无法理解这会如何影响递归；因为每次start开始时i都会被重置，而且每次成功调用move都会导致调用start，所以start中的while循环将永远不会终止！

我想这过程最终可能会访问到每个方格，到那时事情可能会按预期工作，但就目前而言，这太复杂了，甚至无法预测。

try :main()
#except: print "I couldn't handle it" <-Row added to prevent python from returning a huge amount of errors

不太明白你最后那句话的意思，但听起来不是个好兆头——你是在掩盖一个错误，而不是找到根本原因。

我打算稍微修改一下这段代码，看看能否通过减少一些全局状态来让它表现得稍微好一点……稍后会再反馈。

更新：

好的，我按照上面说的去掉了indexes的全局性。然后我把start/restart的递归替换为restart中的无限循环，在start中放了一个return语句，原来调用restart的地方改成了这个，并在start的末尾加了一个sys.exit()（以便在成功时跳出无限循环）。结果的表现更符合预期。虽然这仍然是个糟糕的设计，但现在它能工作了，意思是它会递归尝试很多随机路径，直到每个局部位置都被访问过。

当然，它仍然不会成功；它只是在不断循环。实际上找到解决方案可能需要对这个算法进行更多的重新思考！但遵循我上面的建议应该会有所帮助，至少。