如果原始函數有很多遞歸調用，如何在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)) 

我顛倒了最後三條語句的順序，以保留它們在原始遞歸方法中被評估的順序。這是必要的，因爲附加的最後一件事將是第一件事情。