在 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]

现在要使函数迭代而不是递归，我们需要创建一个队列来存储我们需要部分暂停和稍后重新访问的各种状态和任务。我们不使用递归调用，而是向队列中追加尚待完成的任务，然后是 'recursive' 计算的新任务，然后是 break（或 continue）的新迭代主循环。

def AcumulacionCelda(x,y):
    if Acum[x, y] != NoData:
        return
    Acum[x, y] = 1
    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}
    keys = tuple(product(range(-1,2), range(-1,2)))[::-1]
    queue = [('Loop', (x, y), list(keys))]

    while queue:
        instruction, coords, directions = queue.pop()
        x, y = coords
        if instruction == 'Loop':
            while directions:
                m, n = directions.pop()
                if Direcciones[x+m, y+n] == d[m, n]:
                    queue.append(('Loop', (x, y), directions))
                    queue.append(('Add', (x, y), (m, n)))
                    if Acum[x+m, y+n] == NoData:
                        Acum[x+m, y+n] = 1
                        queue.append(('Loop', (x+m, y+n), list(keys)))
                    break
        elif instruction == 'Add':
            m, n = directions
            Acum[x, y] += Acum[x+m, y+n]

在 Python 中将递归函数转换为非递归函数

Convert a recursive function into Non recursive in Python

python

recursion

iteration

qgis