如果原函数有很多递归调用，如何使递归函数使用while循环？

Question

我将用python演示，因为它很容易阅读。。。。在

    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)

我需要重写这个函数以避免使用递归。但是，它有这种分支属性，这使得它有点棘手。如何构造我的函数以不使用递归？如果你能给我提供while/for循环的基本结构，我相信我可以找到其余的。谢谢。在

Answer 1

创建一个arguments堆栈，它将跟踪您要进行但尚未进行的调用。在通常调用loop的任何地方，都应该推送到堆栈上。一旦arguments为空，就可以返回。在

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))

我颠倒了最后三条语句的顺序，以保持它们在原始递归方法中的求值顺序。这是必要的，因为最后一个附加的内容将是弹出的第一个内容。在