将一个递归函数转换为非递归的Python函数。

Question

我如何将这个递归函数转换并优化为迭代函数呢。我正在尝试编程一个函数，它使用方向图来累积流，但是，对于非常大的方向图，这个函数就会崩溃。我用Python编程，增加系统递归限制不是一个选择。在

def AcumulacionCelda(x,y):
            if Acum[x,y]==NoData:
                Acum[x,y]=1
                for m, n in product(range(-1,2), range(-1,2)):
                    if m==-1 and n==-1 and Direcciones[x+m,y+n]==4:
                        AcumulacionCelda(x+m,y+n)
                        Acum[x,y]=Acum[x,y]+Acum[x+m,y+n]
                    elif m==-1 and n==0 and Direcciones[x+m,y+n]==5:
                        AcumulacionCelda(x+m,y+n)
                        Acum[x,y]=Acum[x,y]+Acum[x+m,y+n]
                    elif m==-1 and n==1 and Direcciones[x+m,y+n]==6:
                        AcumulacionCelda(x+m,y+n)
                        Acum[x,y]=Acum[x,y]+Acum[x+m,y+n]
                    elif m==0 and n==1 and Direcciones[x+m,y+n]==7:
                        AcumulacionCelda(x+m,y+n)
                        Acum[x,y]=Acum[x,y]+Acum[x+m,y+n]
                    elif m==1 and n==1 and Direcciones[x+m,y+n]==8:
                        AcumulacionCelda(x+m,y+n)
                        Acum[x,y]=Acum[x,y]+Acum[x+m,y+n]
                    elif m==1 and n==0 and Direcciones[x+m,y+n]==1:
                        AcumulacionCelda(x+m,y+n)
                        Acum[x,y]=Acum[x,y]+Acum[x+m,y+n]
                    elif m==1 and n==-1 and Direcciones[x+m,y+n]==2:
                        AcumulacionCelda(x+m,y+n)
                        Acum[x,y]=Acum[x,y]+Acum[x+m,y+n]
                    elif m==0 and n==-1 and Direcciones[x+m,y+n]==3:
                        AcumulacionCelda(x+m,y+n)
                        Acum[x,y]=Acum[x,y]+Acum[x+m,y+n]

            return;

for i, j in product(range(1,Filas-1), range(1,Columnas-1)):
      AcumulacionCelda(i,j)

Answer 1

这是这类问题的低层次解决方案。我认为有更好的工具来做这项工作。你可能会想使用Dijkstra的最短路径算法。您可能需要查看NetworkX模块算法部分。将x，y位置映射为网络图中的点，使得边缘上的权重作为x，y城市位置的平方差。在

Answer 2

首先，让我们重构一系列if语句，使递归函数更简单：

def AcumulacionCelda(x,y):
    d = {(-1, -1):  4,
         (-1, 0) :  5,
         (-1, 1) :  6,
         (0, -1) :  3,
         (0, 0)  :  'dummy',
         (0, 1)  :  7,
         (1, -1) :  2,
         (1, 0)  :  1,
         (1, 1)  :  8}

    if Acum[x, y] == NoData:
        Acum[x, y] = 1
        for m, n in product(range(-1,2), range(-1,2)):
            if Direcciones[x+m, y+n] == d[m, n]:
                AcumulacionCelda(x+m, y+n)
                Acum[x,y] += Acum[x+m, y+n]

现在要使函数迭代而不是递归，我们需要创建一个队列来存储我们需要部分挂起并在以后重新访问的各种状态和任务。我们不是递归调用，而是将要完成的任务附加到队列中，然后是用于“递归”计算的新任务，然后将break（或continue）附加到主循环的新迭代中。在

^{pr2}$