Исключение рекурсивного хвостового вызова для разложения квадри в 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)

Я знаю о методах устранения хвостовых вызовов, но примеры, которые я видел, не демонстрируют шаблон разветвления, свойственный рекурсивному разложению на четыре дерева (множественные независимые рекурсивные вызовы хвоста). Моя мотивация - писать код, который не исчерпывает стек, если я использую его на миллионах точек, которые могут демонстрировать существенную кластеризацию, что приводит к очень глубокой рекурсии. Кроме того, я хочу включить временное измерение и реализовать пространственные буферы, чтобы точки могли быть назначены нескольким поддоменам (мне это нужно для дальнейшей обработки). Из-за этого существенного количества настроек существующие реализации дерева квадрантов могут не подходить. Если вам надоел еще один новичок, задающий тот же старый вопрос, продолжайте и хорошего дня, спасибо за чтение. В противном случае вы можете указать мне ресурсы, которые помогут мне решить проблему, или вы можете опубликовать потенциальное решение. Я был бы рад, если бы вы сделали.

Answer 1

В вашем примере, я думаю, вы немного неправильно поняли хвостовую рекурсию. Есть только один хвост, и это будет линия:

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

Таким образом, чтобы открыть эту хвостовую рекурсию, измените if len(inX)... в while len(inX)... и изменить последний разложить на

inX, inY, ... = R4x, R4Y ...