How to apply recursion function in land subdivision?

Question

I've made a subdivision code that allows division of a polygon by bounding box method. subdivision(coordinates) results in subblockL and subblockR (left and right). If I want to repeat this subdivision code until it reaches the area less than 200, I would need to use recursion method.

ex: B = subdivision(A)[0], C = subdivision(B)[0], D = subdivision(C)[0]... until it reaches the area close to 200. (in other words,

subdivision(subdivision(subdivision(A)[0])[0])[0]...)

How can I simplify repetition of subdivision? and How can I apply subdivision to every block instead of single block?

while area(subdivision(A)[0]) < 200:  
    for i in range(A):   
        subdivision(i)[0]

def sd_recursion(x):  
    if x == subdivision(A):  
        return subdivision(A)      
    else:   
        return   

I'm not sure what function to put in

Answer 1

"What function to put in" is the function itself; that's the definition of recursion.

def sd_recursive(coordinates):
    if area(coordinates) < 200:
        return [coordinates]
    else:
        a, b = subdivision(coordinates)
        return sd_recursive(a) + sd_recursive(b)  # list combination, not arithmetic addition

To paraphrase, if the area is less than 200, simply return the polygon itself. Otherwise, divide the polygon into two parts, and return ... the result of applying the same logic to each part in turn.

Recursive functions are challenging because recursive functions are challenging. Until you have wrapped your head around this apparently circular argument, things will be hard to understand. The crucial design point is to have a "base case" which does not recurse, which in other words escapes the otherwise infinite loop of the function calling itself under some well-defined condition. (There's also indirect recursion, where X calls Y which calls X which calls Y ...)

If you are still having trouble, look at one of the many questions about debugging recursive functions. For example, Understanding recursion in Python

I assumed the function should return a list in every case, but there are multiple ways to arrange this, just so long as all parts of the code obey the same convention. Which way to prefer also depends on how the coordinates are represented and what's convenient for your intended caller.

(In Python, ['a'] + ['b'] returns ['a', 'b'] so this is not arithmetic addition of two lists, it's just a convenient way to return a single list from combining two other lists one after the other.)

Recursion can always be unrolled; the above can be refactored to

def sd_unrolled(coordinates):
    result = []
    while coordinates:
        if area(coordinates[0]) < 200:
            result.extend(coordinates[0])
            coordinates = coordinates[1:]
        a, b = subdivision(coordinates[0])
        coordinates = [a, b] + coordinates[1:]
    return result

This is tricky in its own right (but could perhaps be simplified by introducing a few temporary variables) and pretty inefficient or at least inelegant as we keep on copying slices of the coordinates list to maintain the tail while we keep manipulating the head (the first element of the list) by splitting it until each piece is small enough.