如何將此非尾遞歸函數轉換爲循環或尾遞歸版本？

Question

我一直對此很好奇。這實在是很容易的，優雅爲人類創造一個無尾遞歸函數來得到的東西複雜，但速度很慢，而且很容易打的Python遞歸的限制：

def moves_three(n, ini=0, med=1, des=2): 
    '''give a int -> return a list ''' 
    if n == 1: 
     return ((ini,des),) 
    return moves_three(n-1, ini=ini, med=des, des=med) + \ 
      ((ini, des),) + \ 
      moves_three(n-1, ini=med, med=ini, des=des) 

if __name__ == '__main__': 
    moves_three(100) # may be after several hours you can see the result. 
    len(moves_three(10000)) 

那麼，如何改變moves_three到尾遞歸一個或一個循環（更好）？更重要的是，有沒有什麼散文可以談論這個？謝謝。

Answer 1

即使使用迭代形式，這也不會更快。問題不是遞歸限制;你仍然低於遞歸限制的一個數量級。問題是你的輸出的大小是O(2^n)。對於n=100，你必須建立一個大約千億億元的元組。不管你如何建立它，你永遠不會完成。

如果你想將它轉換爲反正迭代中，可以通過管理狀態明確的堆棧，而不是調用堆棧來完成：

def moves_three(n, a=0, b=1, c=2): 
    first_entry = True 
    stack = [(first_entry, n, a, b, c)] 
    output = [] 
    while stack: 
     first_entry, n1, a1, b1, c1 = stack.pop() 
     if n1 == 1: 
      output.append((a1, c1)) 
     elif first_entry: 
      stack.append((False, n1, a1, b1, c1)) 
      stack.append((True, n1-1, a1, c1, b1)) 
     else: 
      output.append((a1, c1)) 
      stack.append((True, n1-1, b1, a1, c1)) 
    return tuple(output) 

混亂，不是嗎？堆棧中的元組(True, n, a, b, c)表示輸入具有參數n, a, b, c的函數調用。元組(False, n, a, b, c)表示在moves_three(n-1, a, c, b)結束後返回到(True, n, a, b, c)呼叫。