Python中四叉树分解的递归尾调用消除

Question

使用Python，是否可以消除四叉树实现中的多个递归尾部调用（转换为迭代），它将点（X，Y）分配给子域（又称叶节点）？ 下面是一个不太假的代码：

def decompose(inX, inY, xmin, xmax, ymin, ymax, maxP): 
#Paramters: Lists of X and Y coordinates, boundaries, max. #points per subdomain

if len(inX) <= maxP: #base case
            --write out list of points and boundaries--
        else:
            xB = (xmin + xmax) / 2 #calculate new boundaries
            yB = (ymin + ymax) / 2

        for  x, y in zip(inX, inY): #assign points to subdomains (a.k.a. children-nodes)
            if x < xB:
                if y < yB:
                    R1X.append(x), R1Y.append(y)
                else:
                    R2X.append(x), R2Y.append(y)
            else:
                if y < yB:
                    R3X.append(x), R3Y.append(y)
                else:
                    R4X.append(x), R4Y.append(y) 

        decompose(R1X, R1Y, xmin, xB, ymin, yB, maxP) #recursive tail calls (which I want to eliminate)
        decompose(R2X, R2Y, xmin, xB, yB, ymax, maxP)
        decompose(R3X, R3Y, xB, xmax, ymin, yB, maxP)
        decompose(R4X, R4Y, xB, xmax, yB, ymax, maxP)

我知道消除尾部调用的方法，但是我看到的examples没有显示递归四叉树分解（多个独立递归尾部调用）固有的fork模式。我的动机是编写代码，如果我在数百万点上使用堆栈，这些点可能会显示大量的聚集，因此会导致非常深的递归。此外，我希望包括时间维度并实现空间缓冲区，以便可以将点分配给多个子域（我需要它来进一步处理）。由于大量的定制，existing quadtree implementations可能不适合。如果你对另一个新手问同样的老问题感到厌烦，那就继续吧，祝你今天愉快，谢谢你的阅读。否则，你可以给我指出帮助我解决问题的资源，或者你可以发布一个潜在的解决方案。如果你这么做我会很高兴的。在

Answer 1

在您的例子中，我认为您对尾部递归有点误解。只有一条尾巴，那就是那条线：

decompose(R4X, R4Y, xB, xmax, yB, ymax, maxP)

所以要打开尾部递归的代码，请将if len(inX)...更改为while len(inX)...，并将最后的分解改为

^{pr2}$