1

Using Python, is it possible to eliminate multiple recursive tail calls (transform to iteration) in a quadtree implementation, which assigns points (X, Y) to subdomains (a.k.a. leaf-nodes)? Here's a not-so pseudo-code:

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)

I am aware of the methods to eliminate tail calls, but the examples I have seen do not exhibit the fork pattern inherent in recursive quadtree decomposition (multiple independent recursive tail calls). My motivation is to write code that does not exhaust the stack if I use it on millions of points that may exhibit substantial clustering, therefore leading to very deep recursion. In addition, I want to include the temporal dimension and implement spatial buffers, so that points may be assigned to multiple subdomains (I need that for further processing). Due to this substantial amount of customization, existing quadtree implementations might not be suitable. If you're bored by just another newbie asking the same old question, go on and have a nice day, thanks for reading. Otherwise you could either point me towards resources that help me solve the problem or you could post a potential solution. I'd be glad if you did.

Happy Tree
  • 11
  • 1
  • You might want to have a look at the y-combinator. It could be possible to build an infinite recursion using it. Usually, you should be able to reformat the code to use forloops instead. – Loïc Faure-Lacroix Jun 30 '15 at 16:40
  • That is something I have not encountered yet. I'll look into it. Thanks for sharing. – Happy Tree Jun 30 '15 at 18:09
  • @Loïc Faure-Lacroix The Y-combinator doesn't eliminate tail-calls. It allows to perform recursive calls from a lambda function but it will keep the size of the Python stack increasing. – Thomas Baruchel Nov 03 '15 at 21:43

1 Answers1

-1

In your example, I think you misunderstand tail recursion a little. There is only one tail and that would be the line: 

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

So to open-code that tail recursion, change the if len(inX)... to while len(inX)... and change the last decompose to 

inX, inY, ... = R4x, R4Y ...
rocky
  • 7,226
  • 3
  • 33
  • 74
  • Thanks for clearing my confusion about tail calls. Not sure I understand the rest of what you write. What you suggest would leave me with 3 recursive function calls and the last line in your answer. The three calls would still exhaust the stack and the last decompose deals only with one quadrant. If you mean to get rid of the three calls I'm still left with the problem that the three other quadrants are not taken into account. – Happy Tree Jun 30 '15 at 18:08
  • Donald Knuth has said that premature optimization is the root of evil. Don't confuse the fact that there may be millions of points with the stack size having millions of points. In general it will have log4(million) which considerably less. So unless you've actually run this code and ran out of stack, first try the simpleminded approach. – rocky Jun 30 '15 at 18:49
  • Anyway, as far as I know, `cpython` doesn't do tail call optimizations. So it wouldn't matter much even if the code had only one tail call. Here: http://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion – Loïc Faure-Lacroix Jun 30 '15 at 19:11
  • The answer shows how you open-code the tail recursion. – rocky Jun 30 '15 at 20:33