是否所有的循環都能用遞歸代替？

01-12

另外想問一下各位大神，while循環和for循環的優點和不足何在？

是。

所有的循環都是等價的。

另：在有些函數式語言中並沒有循環的概念，如Haskell和Scheme里既沒有for循環，也沒有while循環，只能使用遞歸。

如果是尾遞歸在有進行優化的情況下，並不會發生棧溢出，與循環等價。

順便偏個題

C/C++里do while循環有個優點，就是和宏結合使用。

比如有這樣一個宏:

#define foo(x) bar_1(x); bar_2(x)

直接在代碼中調用

foo(something);

這樣沒有問題,但是如下就有可能出問題了:

if(WTF) foo(something);

這時候宏展開是:

if(WTF) bar_1(something); bar_2(something);

出錯啦,使用大括弧將宏包起來也不能完美解決問題

#define foo(x) {bar_1(x); bar_2(x)}

如果有else,這時候宏展開是:

if(WTF) { bar_1(something); bar_2(something); }; else //...

君有見下面的else嗎QAQ

使用do while循環包起來就不會有如上的問題:

#define foo(x) do { bar_1(x); bar_2(x); } while (0)

上面的展開變為:

if(WTF) do { bar_1(something); bar_2(something); } while (0); else //...

問題解決

能不能？能。

結論很暴力，但細說起來還是有點意思的，容我慢慢道來。（贈送循環不變式分析法解釋）

首先我們看一下我們用循環做過些什麼：

還是拿斐波那契數列舉例子，用循環我們通常這麼寫：

//c++11 #include & #include &

int fib1(int n) { int a = 0, b = 1, tmp; for(int i = 0; i &< n; ++i) { tmp = a; a = b; b = b + tmp; } return a; } int main(){ printf("%d ", fib1(10)); return 0; }

可以注意到，在fib1中，我們必須小心處理a，b，tmp三者的賦值順序，以確保下一個狀態的準確。除此以外，i也是迭代過程中需要處理的狀態，這裡只是通過for循環來做了。

那麼如果這時候我要用《演算法導論》上提到的分析「循環不變式」的方法，來分析一下我寫的fib1正不正確，該怎麼做呢？

我們來理清一下，在a，b，tmp，i，n這5個變數中，tmp僅僅是用來解決賦值時的順序問題的，n是常量，真正跟迭代的狀態有關的變數是a，b，i這三個。

所以我們得到循環不變式：a == fib(i) b == fib(i + 1) ，只要我們能證明這個特質在從當前狀態到下一個狀態的過程中能得以保持（以及對初始狀態成立），我們就相當於證明了式子在迭代的每個階段都成立（有沒有發現其實就是數學歸納法？），我們就能確信我們的代碼沒有錯，即當i == n的時候，我們一定能得到a == fib(n)。

為了讓這件事情做得更機械一點，我們把代碼改寫成下面的fib2這樣，把迭代變數a，b，i都暴露出來，並且都通過next_*這些臨時變數來計算下一個狀態，這樣我們就只需要考慮下一個狀態和上一個狀態的關係，而不用關心賦值的順序了（可以注意到對next_*賦值的三條語句的順序是不重要的，對後面三條語句也一樣）。

int fib2(int n) { int a = 0, b = 1, i = 0, next_a, next_b, next_i; //(a, b, i) 構成一個狀態 while(true) { if(i &>= n) { break; } else { next_a = b; //根據當前狀態計算下一個狀態 next_b = a + b; next_i = i + 1; a = next_a; //更新當前狀態 b = next_b; i = next_i; } } return a; }

通過上面的改造，我們發現，在新的fib2中，迭代變數a，b，i已經被明確地暴露出來了，並且對下一個狀態的計算過程很明確，不再是搗鼓一些不明所以的tmp變數了，而且對計算順序也不再敏感。

不過，它顯然沒有fib1簡潔好看。那麼怎麼做到內外兼修呢？可以把迭代變數作為一組參數定義一個函數專門用來迭代，然後這組參數表達的就是當前狀態，在函數體內要做的主要事情，就是1. 判斷是否到達終止狀態， 2. 計算出下一個狀態。這樣一來我們就得到了下面的fib3 。可以看到，我們之前通過next_*變數做的事情，現在被傳參過程中的參數拷貝替代了。

int fib3(int n) { std::function& iter; iter = [n, iter](int a, int b, int i) { if(i &>= n) { return a; } else { return iter(b, b + a, i + 1); } }; return iter(0, 1, 0); }

這樣做好處當然明顯，就是迭代變數一覽無餘，分析程序正確性更容易了。另外，計算下一個狀態的過程中也不需要考慮賦值的順序了，讀寫都方便很多。

但是這樣寫也是會帶來一些問題的，比如遞歸調用需要消耗棧內存空間，這樣一來程序就不可能長時間運行（因為每次迭代都要消耗內存空間）。

不過可以看到，以上的fib3和fib2是直接對應的，對於給出其中任何一種，我們都很容易機械地把它翻譯為另外一種，這種遞歸形式被稱為尾遞歸（見什麼是尾遞歸？ - 編程）。既然人可以容易的在兩種形式之間轉換，那麼機器自然也能，所以在c++里，如果編譯的時候加了-O2的優化選項，這種形式的遞歸是可以僅佔用常量內存空間的。

所以從表達能力的角度考慮，那麼當然是應該把這種沒有副作用的純函數寫成遞歸的形式的。

不過從實際使用的角度看，有相當多的非函數式語言（如Python，JavaScript）是不做尾遞歸優化的，所以在使用的時候也就要考慮這樣寫導致的佔用棧空間的代價，當然在非性能瓶頸處主要考慮的還是表達能力。

為什麼國外的工程師在給單片機做死循環時喜歡用 for(;;) 而不是 while(1)？ - 編程

程序語言中for循環和while循環的深層區別是什麼？ - 編程語言

for-loop 本身就是 while 的語法糖 (Syntactic sugar)。

換句話說，for-loop就是可讀性更強，更直觀的while。

循環使用for循環，while或者do while在一個method中實現的。

遞歸是在一個method中再次調用此method或者調用其他method。然後以此類推，一層一層調用進去，直到遇到return點，再一層一層跳出來。最後執行完整個方法的操作。

循環就是需要一部分內存，然後一直利用這一塊內存的數據進行存儲或提取。如 array或者linkedlist。有的時候會用arraylist或其他長度能夠改變的數據結構。但總之是，一塊內存上的處理。

而遞歸是不斷調用新的方法，所以堆棧塊上不斷積累。

循環和遞歸是相通的。你可以嘗試recursive 和iteratively 遍歷二叉樹。

有關於for循環和while循環，我是寫java的，所以沒什麼大區別，視情況和習慣而定。anyway，都可以改寫，大不得了你先定義i=0，while（i）｛裡面放終止條件｝。

鄙人愚見，有不對地方，望指正！

for循環有一個風格上的優勢，它把所有用於操作循環的表達式寫在一起，便於尋找。當循環體較龐大時，這個優點更突出.——《c和指針》

第一個問題：是！

while(1)的寫法 W4會報一個warningC4127 msdn推薦用for(;;)替代while(1)

scheme里沒有循環，只有遞歸，循環可以通過尾遞歸實現…

1.能用遞歸解的都可以用循環來寫。

2.循環比遞歸的效率高（遞歸每調用一次都要存一份當前function的副本，時間內存都消耗增大）

3.只有在循環寫出來會把人看暈的情況下，優先選遞歸，遞歸使得代碼簡單易懂。

以上引自DEITEL 的《C++ how to program 》，字典一樣，解決很多問題。

能互相替代，只是用遞歸有時候能讓代碼更清晰簡潔，而不是滿屏幕都是亂七八糟對不齊的for循環ㄟ( ▔, ▔ )ㄏ

原理上是一樣的，實現時候會受到一些環境的限制

循環都有如下形式

loop with input(a1,a2,...,an) { Oracle; if(A) break; else continue; } output(a1,a2,...,an)

可以將這個循環變為遞歸

recursive with input(a1,a2,...,an) { Oracle; if(A) return (a1,a2,...,an); else (a1,a2,...,an)=recursive (a1,a2,...,an); return (a1,a2,...,an); }

同樣可以將遞歸變回循環，所以兩者等價。

for循環比較清晰。在一個括弧里把初始化、循環條件、增量都寫出來了。可讀性強。

為什麼沒人回答遞歸的。

循環的次數可以任意次，只要你願意等。

遞歸是需要內存的，一定深度後就會堆棧溢出。