遞歸功能被轉換成非遞歸函數

Question

可能重複：
Can every recursion be converted into iteration?

可以隨時或箱子一個遞歸函數被轉換成非遞歸功能或一組非遞歸函數？

你能指點我的例子哪些工作，不工作？

感謝

Answer 1

這總是可能的，因爲您可以自己模擬調用堆棧。但是，這並不容易。

簡單案例是尾遞歸：這些甚至不需要堆棧。例如，這傢伙被輕易地轉化成for循環：

def countdown(n): 
    if n >= 0: 
     print n 
     countdown(n-1) 

即使功能不是嚴格尾遞歸，有時你可以仍然逃脫不具有棧。例如，經典因子函數：

def factorial(n): 
    if n <= 1: 
     return 1 
    else: 
     return n * factorial(n-1) 

當存在多個遞歸調用時，它變得更加困難。舉個例子，快速排序：

def quicksort(array): 
    if len(array) <= 1: 
     return array 
    else: 
     pivot = array[0] 
     left = quicksort([x for x in array[1:] if x < pivot]) 
     right = quicksort([x for x in array[1:] if x >= pivot]) 
     return left + [pivot] + right 

雖然這是絕對有可能做到這一點沒有遞歸，你就必須自己建立一個棧，並構建while循環，迭代，直到堆棧爲空。

Answer 2

是的，它總是可以遞歸函數轉換成非遞歸之一。

你可以用一個簡單的思想實驗證明了這一點：您可以實施模擬一個圖靈完備的寄存器機堆棧（一個簡單的微處理器的基本等價）一個簡單的非遞歸解釋。這是一個非遞歸的代碼，可以運行任何遞歸函數。

請注意，在遞歸的所有非平凡情況下（即比簡單的尾部遞歸更復雜，可以將其轉換爲循環），您將需要以某種方式捕獲包含在嵌套堆棧幀中的信息。通常，這可以通過使用堆內存來模擬可變大小的堆棧來完成，但也可以使用其他技術（例如延續或隊列）。

Answer 3

是的每個遞歸函數都可以轉換爲迭代函數。

Answer 4

所有的遞歸函數都可以轉換爲迭代函數，但並非如此簡單。

它只是簡單的在尾遞歸的情況。這是當只有一個遞歸調用發生時，它發生在最後。這可以簡單地轉換爲do-while語句。

對於其他情況並非如此簡單。雖然所有遞歸都可以轉化爲迭代，但是您需要在更復雜的示例中模擬自己的堆棧。

Answer 5

總是可以使用stack將遞歸轉換爲迭代。您不必使用某些參數進行遞歸調用，而是將參數集推入堆棧。在每次迭代中，頂部參數集被彈出並處理。