how to make a recursive function use while loops if the original function had many recursive calls?

Question

I'll demonstrate in python because it is easy to read....

    def loop(N,x,y):
        if N < n:                         #condition is defined elsewhere
            side = 1.0 / (2.0**(n+1))
            addTriangle(picture,x,y,side)
            loop(N+1, x - .25*side, y - math.sqrt(.75)/2*side)
            loop(N+1, x + .75*side, y - math.sqrt(.75)/2*side)
            loop(N+1, x + .25*side, y + (side/4.0)*math.sqrt(3))
    loop(0, .25, math.sqrt(.75)/2)

I need to rewrite this function to avoid using recursion. However, it has this sort of branching property that makes it a little tricky. How can I structure my function to not use recursion? If you can provide me the basic structure of while/for loops I'm sure I can figure out the rest. Thanks.

Answer 1

Create an arguments stack which will keep track of the calls you want to make, but haven't made yet. Everywhere you ordinarily call loop, instead push onto the stack. Once arguments is empty, you can return.

def loop(N, x, y):
    arguments = [(N, x, y)]
    while arguments:
        N, x, y = arguments.pop()
        if N < n:
            side = 1.0 / (2.0**(n+1))
            addTriangle(picture,x,y,side)
            arguments.append((N+1, x + .25*side, y + (side/4.0)*math.sqrt(3)))
            arguments.append((N+1, x + .75*side, y - math.sqrt(.75)/2*side))
            arguments.append((N+1, x - .25*side, y - math.sqrt(.75)/2*side))

I reversed the order of the last three statements, to preserve the order they were evaluated in in the original recursive method. This is necessary because the last thing appended will be the first thing popped.