所有遞歸都可以改寫成循環嗎？
話說遞歸層次比較深的話容易造成stack overflow,還被認為效率不高，而且有人表示所有的遞歸都可以改寫成循環，這是真的嗎？
林銳博士的書中曾表示：所有的遞歸都可以改寫成循環，而且認為遞歸的效率不高。而王垠博士則認為遞歸比循環強。「遞歸的數據總是需要遞歸的程序來處理。雖然遞歸有時候表現為另外的形式，比如循環(loop)，但是「遞歸」這個概念比「循環」更廣泛一些。有很多遞歸程序不能用循環來表達」
http://blog.sina.com.cn/s/blog_5d90e82f01018ge9.html
「而其實遞歸比循環表達能力強很多，而且效率幾乎一樣。有些程序比如解釋器，不用遞歸的話基本沒法完成。」http://blog.sina.com.cn/s/blog_5d90e82f01015271.html王垠寫解釋器可是很在行的啊，對循環，遞歸的理解也應該不錯吧。
在此請教各位啦.
他們的說法放到他們各自的場景中都是正確的。
林銳是基於他所掌握的有限的語言來提出思路，是工程師思路。他主要掌握的語言是 C 語言，在 C 語言中如果使用 C 語言函數實現遞歸，確實效率不高，而且現實中那些難以變成循環的遞歸很少需要一個工程師去實現，故而，他表達的觀點在他所處的應用場合中正確。
而王垠是站在科學家的角度考慮問題，把編程語言作為一門學問去看。他站得更高，看得更遠，得出的結論也更具有普適性。很多語言中遞歸的性能並不差，而且正確實現尾遞歸的語言不存在棧溢出問題。
如果要打一個比方的話，可以認為林銳的觀點是經典物理，而王垠的觀點是相對論。相對論能夠在更廣泛的場合中適用，也更準確更科學。但經典物理在其特定領域的應用是很好的，並沒有被相對論淘汰。是的。準確的說：所有遞歸都可以用非遞歸的方式實現。至於是不是循環，則方式各異。遞歸的本質是壓棧，循環中加上棧操作，其實和遞歸沒有本質區別。而且，遞歸問題用非遞歸的方式去解，並不會從本質上降低問題層次的深度。寫的不好一樣會有溢出的問題。
在計算開始之前就能確定層數，而且遍歷順序無所謂的情況下的遞歸都該被改成循環。對於有順序的情況，比如遍歷一棵任意的樹來釋放樹上的所有節點的資源，而且必須從葉子開始釋放時，用遞歸來實現這種順序就比較好，用循環的話性能無法提升而且可讀性大打折扣。
實際的項目中，如果是用c/c++/java這一類的常規的語言來開發的話，其實有一個很現實的問題: 遞歸很難調試。設了斷點也不知道到底到了哪一層；檢查個變數也不知道是哪一層的；系統幫你維護了一個堆棧，但是這個堆棧是代碼和數據共用的，無法直觀的查看。
對於這種情況，能用循環的就盡量用循環，好調試、好維護，其實代碼量差不多。遞歸的不可控因素比較多。對於LISP/erlang/prolog這種鼓勵遞歸的語言，當然要用遞歸。不過，接下來要說到另外一個問題。－－－－－－－－－－－－－－－－－－－－－－－－－某些比較難懂的演算法，不管你是用循環還是遞歸，可能都很難懂，難讀，難調試! 所以，儘可能封裝起來，獨立起來，不要暴露到外面，可以單獨測試、單獨調試。上層調用的時候，才不要關心底層用的是循環還是遞歸呢。剛開始可能用遞歸，後來代碼重構的時候改成循環了；或者改回來也說不定。－－－－－－－－－－－－－－－－－－－－－－－－－@徐峰 你這個說法給了我很大啟發。不過更客觀一點說，有很多程序員確實比較依賴斷點來調試，也確實很快解決問題了。對於他們來說，那麼能採用循環來代替遞歸的話確實是更好的選擇。不同的程序員養成了不同的習慣，也不好說哪種對哪種錯，掌握多了，實踐中可以評估代價，靈活選擇。也有的人就是習慣了遞歸的思路，要改成循環反而不知所措，我剛開始學編程的時候就有這種趨勢，認為遞歸是更高級的東西所以寫一段精鍊的遞歸代碼就洋洋得意...到了後來，有能力把很多遞歸代碼用循環的方式寫出來，就更得意了...現在呢，我寫ruby的時候就直接用vim, 靠測試代碼來保證質量；寫ios的時候就是xcode, 斷點調試，你讓我換過來用我還真不知道怎麼辦...
如果從代碼層次講的話，
這個問題的答案是肯定的， 所有遞歸都可以轉化成循環， 不過需要一個相應的堆棧結構的數據。因為本質上講， 遞歸和循環都是上一輪和下一輪執行相同的操作， 唯一不同的區別是， 遞歸有參數的歷史記錄， 循環沒有（如果你沒有手工記錄的話）。 那麼很自然， 你在循環中引入一個堆棧結構， 手工壓棧， 這樣循環變數（或參數） 也就有了歷史記錄。 這樣， 所有的遞歸都可以用循環來代替。但是正如 @高木端 所言， 數學意義上， 手工遞歸也是遞歸了。 所以， 真正達到轉化的效果是不行的。
實際很多情況下， 循環和遞歸有種逆向思維關係， 循環通常來自底向上， 遞歸自頂向下。 他們之間可以轉化。我個人更傾向於使用遞歸， 因為遞歸清晰明了。 優化的時候， 我才去轉化。其實嘛，只要理解了為什麼正則表達式的計算能力不如上下文無關文法，就理解了為什麼不是所有的遞歸都可以在不藉助遞歸數據結構（譬如說維護自己的棧）的情況下化解為循環了。
剩下的請看《Parsing Techniques》用循環壓棧來避免遞歸也太搞笑了點吧，手工遞歸就不是遞歸了？
遞歸化循環是對演算法的優化，比如計算Fibonacci 數列的值，F（n）=F（n-1)+F(n-2);F(0)=1;F(1)=1;
要算F(100),你可以從F（100）遞歸往下算，也可以從F（2）開始循環往上算。遞歸化循環是要通過演算法的優化避免壓棧操作，而從棧底向上循環得到結果。棧底不可預見的時候，遞歸是無法有效地化為循環的。If you maintain your own stack it would be correct. Otherwise recursion can do things loops can"t, like walk a tree.[http://c2.com/cgi/wiki?RecursionVsLoop]有限遞歸都可以轉換為迭代
補充一下，遞歸和循環壓棧有區別吧，循環壓棧是在同一個函數環境下，遞歸則是不停調用函數，調用函數有成本。
答案: 並一定. 但是 遞歸演算法一定可以轉換成為非遞歸演算法, 有些可以用循環解決, 有些複雜的遞歸是不行的, 一般用棧來解決.
遞歸演算法向非遞歸演算法轉換
摘自:遞歸演算法和非遞歸演算法的區別和轉換
遞歸演算法實際上是一種分而治之的方法，它把複雜問題分解為簡單問題來求解。對於某些複雜問題(例如hanio塔問題)，遞歸演算法是一種自然且合乎邏輯的解決問題的方式，但是遞歸演算法的執行效率通常比較差。因此，在求解某些問題時，常採用遞歸演算法來分析問題，用非遞歸演算法來求解問題；另外，有些程序設計語言不支持遞歸，這就需要把遞歸演算法轉換為非遞歸演算法。
將遞歸演算法轉換為非遞歸演算法有兩種方法，一種是直接求值，不需要回溯；另一種是不能直接求值，需要回溯。前者使用一些變數保存中間結果，稱為直接轉換法；後者使用棧保存中間結果，稱為間接轉換法，下面分別討論這兩種方法。
1.
直接轉換法
直接轉換法通常用來消除尾遞歸和單向遞歸，將遞歸結構用循環結構來替代。
尾遞歸是指在遞歸演算法中，遞歸調用語句只有一個，而且是處在演算法的最後。例如求階乘的遞歸演算法：
long
fact(int n)
{
if
(n==0) return 1;
else
return n*fact(n-1);
}
當遞歸調用返回時，是返回到上一層遞歸調用的下一條語句，而這個返回位置正好是演算法的結束處，所以，不必利用棧來保存返回信息。對於尾遞歸形式的遞歸演算法，可以利用循環結構來替代。例如求階乘的遞歸演算法可以寫成如下循環結構的非遞歸演算法：
long
fact(int n)
{
int
s=0;
for
(int i=1; i&<=n;i++)
s=s*i;
//用s保存中間結果
return
s;
}
單向遞歸是指遞歸演算法中雖然有多處遞歸調用語句，但各遞歸調用語句的參數之間沒有關係，並且這些遞歸調用語句都處在遞歸演算法的最後。顯然，尾遞歸是單向遞歸的特例。例如求斐波那契數列的遞歸演算法如下：
int
f(int n)
{
if
(n= =1 | | n= =0) return 1;
else
return f(n-1)+f(n-2);
}
對於單向遞歸，可以設置一些變數保存中間結構，將遞歸結構用循環結構來替代。例如求斐波那契數列的演算法中用s1和s2保存中間的計算結果，非遞歸函數如下：
int
f(int n)
{
int
i, s;
int
s1=1, s2=1;
for
(i=3; i&<=n;
++i)
{
s=s1+s2;
s2=s1;
// 保存f(n-2)的值
s1=s;
//保存f(n-1)的值
}
return
s;
}
2.
間接轉換法
該方法使用棧保存中間結果，一般需根據遞歸函數在執行過程中棧的變化得到。其一般過程如下：
將初始狀態s0進棧
while
(棧不為空)
{
退棧，將棧頂元素賦給s;
if
(s是要找的結果)
返回;
else
{
尋找到s的相關狀態s1;
將s1進棧
}
}
間接轉換法在數據結構中有較多實例，如二叉樹遍歷演算法的非遞歸實現、圖的深度優先遍歷演算法的非遞歸實現等等。
使用非遞歸方式實現遞歸問題的演算法程序,不僅可以節省存儲空間,而且可以極大地提高演算法程序的執行效率。本文將遞歸問題分成簡單遞歸問題和複雜遞歸問題;簡單遞歸問題的非遞歸實現採用遞推技術加以求解,複雜遞歸問題則根據問題求解的特點採用兩類非遞歸實現演算法,使用棧加以實現。
這個問題要回答完整，需要很多精力和時間。我先回答一部分。然後持續補充。
（1）遞歸都可以改成循環。這個命題如何評價？
我先說下結論，就是，這個命題是成立的，但是，如果只看到這個結論，對問題的認識則是片面的，不完整的。
也就是說，只看到了遞歸和循環的共同點：都是 EIP 在同一段代碼段內反覆。
而沒有注意到兩者在模型，重複代碼段之間的層次結構，和流程式控制制方面的差異。
同時有很多命題加強了這種暗示，比如，遍歷樹，有非遞歸實現。比如說，我自己的技術博客上的文章：
採用棧數據結構的二叉樹非遞歸遍歷
採用路徑模型實現遍歷二叉樹的方法[非原創]樹和圖的遍歷但是，它忽略了另一個層面，就是遞歸和循環的思維模型上的差異性。
我先打個比喻，遞歸是自相似的，就好比分形圖，兩次重複代碼段之間，是有結構，層次上的「父子」關係的。我用滑鼠手繪了一個草圖，不是那麼完美，感受一下就好（下圖是主觀感受示意，可能不太嚴謹的）：
而循環呢，思維模型里，它是每層循環是在一個維度上的。
遞歸在重複的代碼片段內，每一層，都有自己獨立的一套上下文。在堆疊。
循環，是在同一個層次之內的。所以，由於這種模型上並不是完全匹配，所以雖然可以相互轉換，但是實際上演算法內部是有一定的「重新加工」的過程。
先舉一個遞歸函數，改成非遞歸函數的例子，釋放一顆二叉樹，假設節點都是用 malloc，realloc 函數分配的，遞歸版本如下（思維是顯而易見的）：
struct NODE { ...; NODE *left, *right; };
typedef struct NODE* LPNODE;
void FreeTree(LPNODE pNode)
{
if(pNode)
{
FreeTree(pNode-&>left);
FreeTree(pNode-&>right);
free(pNode);
}
}
改成非遞歸，當然有很多方式，在遞歸中，是最後釋放根節點，在改成非遞歸的時候，我們可以最後釋放根節點，也可以立刻就釋放當前節點，只要有 stack 幫我們記著之後需要釋放的節點就好辦了，我們可以套用按層次（深度）遍歷的非遞歸方法，就很容易寫出：
LPNODE stack[256];
int top = -1;
void FreeTree(LPNODE pNode)
{
LPNODE p1 = NULL;
top = -1;
if(pNode)
stack[++top] = pNode;
while(top &>= 0)
{
p1 = stack[top--];
if(p1-&>left) stack[++top] = p1-&>left;
if(p1-&>right) stack[++top] = p1-&>right;
free(p1);
}
}
可以看到，這個例子中，在解決問題的思維上有微小的差異，或者說，在彙編級別上並不是對等的。在遞歸版本中，根節點最後被釋放，而在非遞歸版本中，根節點第一個就被釋放了。
也就是說遞歸和循環之間，沒辦法像 while 和 for 循環之間轉換的那麼簡單且直觀。為什麼呢，因為兩者在這種結構上有差別。
說的更細一些，就是兩者指令流控制在高級語言層面不直接對等。
此外，就是遞歸的上下文（stack frame）會切換，循環不會切換（位於相同的 stack frame）。循環主要是通過 continue 和 break 以及 jmp，本質上都是通過跳轉來控制 eip 的。在高級語言層面上，一次循環不直接從（循環體）的中間開始。
for ( i = 0 ; i &< n ; |-&> i++ --| ) //or while (...)
{ | |
... ; &<-----------+---------|
... ; |
continue; --------&>|
... ; |
break;-------| |
... ; | |
... ; -------+----&>|
} |
|
...; &<---------|
而遞歸是通過 call 和 ret，也就是說，加上了 stack 的輔助來控制 eip。使得它可以從重複代碼段（循環體）的中間繼續運行。
void foo ( arg x )
{
... ; &<-----------|
... ; |
ret ; -------------+----|
... ; | |
foo ( f(x) ); -----| |
... ; &<--------+--------| //這個跳轉是比較特殊的
... ; |
... ; |
ret ; ---------|
}
可見，遞歸通過 ret 可以回到重複代碼段的中間位置（由 stack 負責記憶），這個跳轉，就是遞歸相對於循環比較特殊的地方，也導致，遞歸改成循環的困難點。
所以，為了把遞歸改成循環，在下面的例子里，我在高級語言中模擬出遞歸的這種流程式控制制。也就是通過 switch - case 語句模擬遞歸中 ret 的效果，讓指令從被「記憶"的循環體中間位置繼續運行。
這一次，舉個通用的例子，來說明，遞歸可改寫成循環這個命題為何可以成立，就是演算法我是不動的，只是在高級語言層面把遞歸函數的痕迹給「抹掉」，是不變應萬變的那種，而基本上你們在書本上等地方看到的遞歸 改
非遞歸，實際上都在演算法上做了一些調整變化的（也就是說遞歸和非遞歸之間，是有有一定的不同）。
用斐波那契數來為例（具體什麼遞歸函數無所謂），當然，如果我是用這樣的循環，是1+1得到2，然後1+2=3, 2+3=5, 3+5=8, 5+8=13 。。。這樣逐個累加得到的，那麼其實演算法和遞歸已經發生了變更。是不足以說明兩者的相互轉換關係的，所以我要求的是，演算法不變，只是在高級語言層面，你看不到遞歸函數的存在而已。
在改寫的時候，謹記：call 對應著在 stack 上 push 當前層次的「狀態」信息，ret 對應於從 stack 上刪除當前層次的「狀態」信息，對應於 pop 操作。然後把彙編偽碼，改成等效高級語言（這樣你就看不到遞歸函數在高級語言層面的存在了，而演算法本質上是不變的）：
因此，我先寫出下面的彙編層面的偽代碼：
當前層次 stack frame：
參數n 返回地址 臨時變數（存儲 f(n-2))
----------------------------------------
| n | retaddr | x1 | 棧增長方向 ----&>
----------------------------------------
|
top
n = stack[top-2]; //arg;
retaddr = stack[top - 1]; //指令流程式控制制
x1 = stack[top]; //f(n-2);
fab(int n)
{
1 if(n &<= 1)
2 {
3 eax = 1;
4 ret;
5 }
6 push n-2;
7 call fab;
8 x1 = eax;
9
10 push n-1;
11 call fab;
12 eax = eax + x1;
13 ret;
}
OK，每行偽代碼前面的數字，模擬的是彙編指令地址，然後我可以根據這個偽代碼，改寫成所謂的「循環」，實際上這個循環就是，一直循環執行指令，直到 stack 空了為止。下面是 C++ 的非遞歸等效代碼：完全模擬上面的偽彙編的過程：
int stack[256];
int top = -1;
void push(int x)
{
++top;
stack[top] = x;
}
int pop()
{
int x = stack[top];
--top;
return x;
}
int fab(int n)
{
int eax = 0;
int eip = 1;
int retaddr;
top = -1;
//初始化 stack
push(n); //分配參數 n
push(1); //壓入返回地址（此處的值 1 無意義）
push(-1); //分配臨時變數 x （此處的值 -1 無意義）
while(top &>= 0)
{
switch(eip) //模擬指令地址
{
case 1:
if(stack[top - 2] &<= 1)
{
eax = 1; //return 1;
pop(); //釋放臨時變數 x
eip = pop(); //彈出返回地址
pop(); //釋放參數
break;
}
case 6:
push(stack[top - 2] - 2); //call f(n-2);
push(8); //壓入返回地址：8；
push(-1); //分配臨時變數 x
eip = 1; //call fab
break;
case 8:
stack[top] = eax; //x = f(n-2);
push(stack[top - 2] - 1); //call f(n-1);
push(12); //壓入返回地址：12；
push(-1); //分配臨時變數 x
eip = 1; //call fab
break;
case 12:
eax = eax + stack[top]; //return f(n-1) + f(n-2);
pop(); //釋放臨時變數 x
eip = pop(); //彈出返回地址
pop(); //釋放參數
break;
}
}
return eax;
}
int _tmain(int argc, _TCHAR* argv[])
{
int x = 6;
int y = fab(x);
printf("fab(%d)=%d
", x, y);
return 0;
}
由此可見，遞歸都可以改成「循環」，命題成立。
我還有另一個關於遞歸函數的回答，裡面有一個 gui 程序，模擬了遞歸函數的執行過程：
C語言中遞歸問題？ - 知乎用戶的回答（2）再說循環改遞歸，這個相對簡單，比如說，循環比較常見的就是，讓一段代碼執行 N 次，我們可以寫成：
for(int i = 0; i &< n; i++)
{
//...循環體
}
這裡循環體可以和 i 沒有任何關係。（當然，也可能發生關係）。
那麼把它改成遞歸就很顯然：void foo(int i)
{
if(i &< n)
{
//... 循環體
foo(i + 1);
}
}
foo( 0 );
當然，循環中臨時變數在循環過程中始終可見的，在循環中可以反覆操作相同的數據。而遞歸函數切換 stack frame ，兩層調用之間的臨時變數都是彼此獨立的，可以在遞歸版本中，傳變數地址來操作同一個數據。
（3）遞歸函數效率比非遞歸的低。
從空間效率上，要看你怎麼看這個問題，我以為是難以給什麼絕對的優劣的結論，要看程序員的權衡和把握。遞歸會對棧有一點壓力，如果在現實中把棧給撐爆了，那麼是不是可以說明程序員對他的代碼的運行效率太遲鈍太麻木了點呢？
需了解，stack 不是用來給你存放需要佔用大內存的數據的，而是存放生命周期短，占內存也不大的臨時數據。
在怎麼樣的情況下，棧會爆掉？你可以自己估算，比如說，默認棧大小是 1MB，你在遞歸函數里申請 1KB 的棧上空間（例如寫一個 char s[1024]; )，如果這個遞歸函數的最大調用深度達到 1000 以上，就導致 stack overflow。
在時間效率上呢，遞歸函數多了很多函數調用，當這些函數調用的數量較大時，它就會積聚成為一個時間成本，因此，這句話是成立的。（函數調用是有成本的）。
我曾經幫一個同學，給他寫了一個馬踏棋盤演算法的非遞歸版本，實際上演算法和遞歸版本是完全一致的，據他和我反饋，說非遞歸版本的速度要比遞歸函數的快。演算法我是沒動的，那麼我想，兩者的時間效率差異，就應該是由函數調用產生的開銷。
好吧，我想說的還有很多，我會慢慢補充。我覺得有必要指出這個問題首先是一個理論問題：就是說，遞歸結構和循環結構的計算能力，是不是一樣的。其次，才是在實際工作中怎樣使用的問題。面對實際問題，兩種結構當然是各有千秋。關於遞歸結構和循環結構的計算能力是否一樣，要回答這個問題首先要知道什麼叫做「計算能力一樣」。用可計算性理論的術語，應當是說這兩種計算模型所計算的函數類是相同的。一些常見的計算模型如圖靈的圖靈機，丘奇的
尾遞歸寫法可以節省棧內存和代碼行數。需要編譯器支持
遞歸思想，可以轉化為遞歸程序，也可以轉化為循環程序，對於計算機來說，不管是編譯器還是手工乾的雜活區別只是有精有粗罷了，不會有太大起伏，反正就那點運算量。
@vczh 的答案是一針見血的！循環和遞歸的相互轉換涉及到圖靈完備性問題。即你要用簡單的循環來代替遞歸的話有時必須要手工維護一個遞歸數據結構（處理上下文無關文法的下推自動機就是比處理正則文法的有限狀態自動機多了一個棧）。而遞歸自然得將這個數據結構隱藏在了調用棧之中，所以它是一種更高級的抽象手段。
遞歸是編程語言中最為優雅的特性，沒有之一！任何反對遞歸的人都是反動派！某些人害怕遞歸只不過是因為某些特定情況下遞歸的結果不可預知而已。其實呢，在執行機制上，遞歸和循環並沒有什麼不同，理論上確實任何遞歸都可以轉換成循環。也就是說，遞歸會出問題的話，循環也一定會出問題，只不過遞歸是出了問題才告訴你，而循環則在執行前就可以知道有問題。
是的，從彙編的角度看，都是轉移指令。
拿來舉例的階乘、斐波那契數列、二叉樹的遍歷，都是已知循環次數的或循環終止條件，此類問題往往即可看成遞歸的問題也可看成迭代的問題（二叉樹的深度優先遍歷就是一種迭代演算法，因為已知循環終止條件，即葉子節點），用遞歸實現只是更易懂而已，循環演算法的實現也不是所謂遞歸轉循環，只是本身就有迭代的特性。而如遍歷一個json對象，jsonObject對象可以包含jsonArray、jsonObject，jsonArray可以包含jsonArray、jsonObject，這種問題無法看做迭代的問題，因為無法提取出循環終止條件，因此無法用迭代演算法實現。而所有遞歸演算法的確能用循環解決，因為可以自己構造棧，以棧空間為循環條件，把函數調用的過程迭代化。
應該說不是所有用遞歸演算法解決的問題都有對應的迭代演算法，但是所有的遞歸都能轉循環！！！
附遍歷json的遞歸方法：
public static JSONArray dealJsonArray(JSONArray jsonArray){
for (Object obj : jsonArray) {
if(obj instanceof JSONObject) {
dealJsonObject((JSONObject)obj);
} else if(obj instanceof JSONArray) {
dealJsonArray((JSONArray)obj);
} else {
System.out.println("list："+obj.toString());
}
}
return jsonArray;
}
public static JSONObject dealJsonObject(JSONObject jsonObject){
Set&
for (Entry&
String key = entry.getKey();
Object val = entry.getValue();
if(val instanceof JSONObject) {
dealJsonObject((JSONObject)val);
} else if(val instanceof JSONArray) {
dealJsonArray((JSONArray)val);
} else {
System.out.println(key+"="+val.toString());
}
}
return null;
}
一個通過模擬stack解決任何recursion轉iteration的方法：https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/recursionConversion/page/recursionConversion.html
推薦閱讀：
※如何評價「消逝的光芒」這款遊戲 ？
※使用「天河二號」超級計算機玩遊戲會是什麼感覺？
※計算機專業女孩子應該往什麼方向發展？
※野指針危害真的很大嗎？
※為什麼以前上機課要戴鞋套？