Устранение рекурсивного вызова хвоста для декомпозиции quadtree в Python

Question

Используя Python, можно ли исключить несколько рекурсивных хвостовых вызовов (преобразование на итерацию) в реализации quadtree, которая присваивает точки (X, Y) субдоменам (aka leaf-nodes) ? Вот не так псевдокод:

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

Answer 1

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

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

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

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