c++ - 请问循环能代替所有递归吗？

Question

之所以会有这种想法，基于两个理由：

递归本质上是在进行压栈操作，人脑不易理解，尽管很多人都在尝试，相比之下，循环就容易理解多了。

这有一篇文章深入地介绍了递归，http://blog.csdn.net/theknotyouknow/article/details/24435291
循环执行效率比递归高很多。

在知乎上搜了一下，感觉回答的并不是很好，还请各位不吝赐教。

怪我咯 · Answer

能。大學計科有講這個的。而且反過來也成立。

你想啊，遞歸呼叫就是把參數壓棧。改成循環，我手動建個棧，每次循環把需要的資料壓進去，循環完彈出來不就可以了麼。

遞迴 vs 循環：

人腦不易理解？你看看著名的斐波那契數列的遞歸定義，寫成遞歸容易還是循環容易？哪個容易理解取決於你的問題的解是怎麼表達的。如果你是解的提出者怎麼辦？習慣了哪個你一定會自然而然用哪個。循環在程式設計界一直是大多數，所以嘛，你懂了？
普通遞歸總是要壓棧的。遞歸的層數多了，棧就要爆了。怎麼辦呢，有一種叫尾遞歸的最佳化，也叫尾呼叫。就是每次到返回前的最後一步才進行遞歸調用，這樣的情況就可以保持棧不隨著遞歸過程一直增長。不僅高效，還直覺。但是很多問題的尾遞歸解本身並不直觀。

高洛峰 · Answer

當然能。

所謂遞歸無非就是函數（直接或間接）呼叫自己，所以我們先看一下簡單的函數呼叫。
假設有一個函數長這樣：

int foo() {
  int X = 4
  int Y = bar(14);
  return X*Y;
}

你可以把它變成這樣：

int foo() {
  foo_stack_frame = gcalloc { X: int; Y: int }
  foo_stack_frame->X = 4;
  foo_stack_frame->Y = bar(14);
  return foo_stack_frame->X * foo_stack_frame->Y;
}

其中gcalloc就是指從GC heap上分配一個什麼東西，這裡分配的是一個map，用於保存foo的stack frame。
然後，foo可以變成這樣：

int foo(continuation C) {
  foo_stack_frame = gcalloc { C: continuation; X: int; Y: int }
  foo_stack_frame->C = C;
  foo_stack_frame->X = 4;
  continuation Next = { foo2, foo_stack_frame };
  return bar(Next, 14);
}

int foo2(continuation C, int Y) {
  foo_stack_frame = C->stack_frame;
  foo_stack_frame->Y = Y;
  continuation Next = foo_stack_frame->C;
  return Next->F(Next, foo_stack_frame->X * foo_stack_frame->Y);
}

這裡的continuation你可以認為就是一個“返回地址”，這個等下再說。
你很可能會問，這麼一大堆變換到底是乾神馬？
嗯，其實這一堆就只變換乾了一件事，那就是──把所有的函式呼叫變成tail call了。
大家都知道，tail call是可以直接優化成goto的，所以我們必須記錄原本的回傳位址，把它傳遞給被tail call的函數，這樣它就可以在結束的時候直接回到最初的呼叫者那裡。
如果對每個函數都做這樣的變換，讓每個函數呼叫都是tail call，那我們就徹底幹掉了stack，整個程式只用goto就搞定。

PS. 對上面內容有興趣的童鞋可以去看看 http://en.wikipedia.org/wiki/Continuation-passing_style
PPS. 其實從「理解」這個角度而言，遞歸往往更容易更清晰，因為它天生就是一個把高複雜度問題分解為低複雜度的過程。

天蓬老师 · Answer

所有遞歸都能寫成尾遞歸嗎？
所有尾遞歸都能寫成迴圈嗎？

如果上面兩個問題的答案都是yes，那就得到了一個構造證明方法。

怪我咯 · Answer

通過棧，所有遞歸都能變成循環。高階語言只是把語言層級的遞歸變成實作層級的堆疊。這個問題在網路上有很詳細的論文。用google搜尋recursion iteration會發現相當多的答案。
用堆疊來實現將遞歸變成循環並不能帶來效能的最佳化，在同種語言的條件下比較更可能帶來效能的損失。
有的遞歸不需要增加棧。去掉了堆疊和堆疊操作可以帶來速度和空間兩方面的效率提升。這其中的一類叫尾遞歸，有的語言實現了尾遞歸優化，也就是自動將尾遞歸變成循環同時不增加棧。例如lisp，scheme，haskell等很多語言都實現了這種優化，但是大多數動態語言包括python，javascript，ruby都沒有，因此這些語言經常會報告遞歸函數超過最大棧深度的錯誤。
我正在做的一個語言，其中一個特性是在支援尾遞歸的優化的同時還要支援某些非尾遞歸的優化，將遞歸函數轉換成不用棧的循環（當然只是一部分，因為不用棧是不可能將所有函數轉換成循環的）。
如sum = (x) -> if x=0 then return 0 else return x+f(x-1)
這個函數是非尾遞歸的，因為遞歸呼叫函數之後還做了加法。
轉換成尾遞歸是這種形式：sum = (x, acc) -> if x=0 then return acc else return f(x-1, acc)
現在的某些語言會自動把後面這種函數變成循環，同時堆疊不增加。也就是類似如下的程式碼
sum = (x, acc) -> while 1 if x=0 then return acc else acc += x
我做的語言將自動把非尾遞歸的版本變成如下的循環：
sum = (x) -> sum = 0; while 1 then if x=0 then return sum else x--; f += x
補充說明一點: 我這裡提供的並不是偽代碼，全部都是我將要發布的語言中的合法代碼。

大家讲道理 · Answer

不只loop能夠取代recursion, 而且還可以根據recursion的公式,直接推倒Genrating Function求值.
比如說Fibonacci, f(n)=f(n-1)+f(n-2),他的closed form就是 F(n) = n / (1-n-n^2)

參考:
http://en.wikipedia.org/wiki/Fibonacci_number
http://www.austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci- numbers.html
http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/Slides/Generating-Functions.pdf