寫尾遞歸函數有什麼規律或技巧嗎？
最近在學習Scala, 學到尾遞歸演算法，個人感覺寫遞歸演算法比較容易，但寫出尾遞歸比較困難，想請教下各位，除了多練習外，寫出尾遞歸演算法是否有可遵循的規律或技巧?
謝邀！如下斐波那契數列n項的一般遞歸寫法：
def fib_1(n: Int): Int = {
if(n &< 2) n
else fib_1(n - 1) + fib_1(n - 2)
}
println(fib_1(10))
要轉為尾遞歸，就必須明確：
尾遞歸就是把一個依賴上一層環境的遞歸(本例中的fib_1) 轉變為一個不依賴上一層環境的遞歸(如下的fib_2), 轉變的方法就是把需要用到的環境通過參數傳遞給下一層：
def fib_2(n: Int): Int = {
@tailrec
def fib(n: Int, acc1: Int, acc2: Int): Int = {
if (n == 0) acc1
else fib(n - 1, acc2, acc1 + acc2)
}
fib(n, 0, 1)
}
println(fib_2(10))
尾遞歸的本質，其實是將遞歸方法中的需要的「所有狀態」通過方法的參數傳入下一次調用中
update: 上述fib_2寫法就是tail-rec形式（a function, as its last operation, returns the result of calling itself），它可以被應用Tail call optimization （由於遞歸在方法的末尾，因此方法中的局部變數已經毫無用處，編譯器完全可以將其「復用」，並把尾遞歸優化為「循環」方式）
顯然不是所有演算法都可以寫出像fib_2這樣的尾遞歸形式，參考：尾遞歸與Continuation我們可以用FP的CPS寫法(In general, you can translate any program into CPS)：
def fib_3(n: Int): Int = {
def fib(n: Int, cont: Int =&> Int): Int = {
if(n &< 2) cont(n)
else fib(n - 1,
r1 =&> fib(n - 2,
r2 =&> cont(r1 + r2)))
}
fib(n, x =&> x)
}
println(fib_3(10))
寫成尾部調用的形式，理論上我們控制了continuation 或函數返回點之後，是可以將棧空間拍扁的（參考：函數式編程與Continuation/CPS -- 簡明現代魔法）
然而Scala doesnt have full tail-call optimization，上面雖然形似尾遞歸，但是在scala里還是可能會SO，編譯器不支持對它做TCO。(經@obovgood提醒，如上CPS形式的尾遞歸，大部分語言編譯器都不支持對其做TCO，除非我們做出一些轉換，手動去寫CPS形式 tail-rec 的TCO，參考如下做法：淺談尾遞歸的優化方式，或Continuation-passing and tail call elimination in Javascript )不過不要急，上面的CPS方式，本身在語義上也不怎麼直觀，Scala有自己的解決之道：import scalaz._, scalaz.Free.Trampoline
import Trampoline._
def fib_4(n: Int): Trampoline[Int] =
if (n &<= 1) done(n) else for {
x &<- suspend(fib_4(n - 1))
y &<- suspend(fib_4(n - 2))
} yield x + y
println(fib_4(10).run)
與最初的fib_1版本比較，我們只修改了函數返回值，返回改為了done，遞歸調用前加了suspend，原理在這裡：http://days2012.scala-lang.org/sites/days2012/files/bjarnason_trampolines.pdf
type Trampoline[A] 其實就是個 Free[Function0, A]，沒錯，是個Free Monad（這就是為啥fib_4有for-yield），也就是說fib_4函數執行時，返回的是一段可被執行的AST/數據結構，有點類似thunk，（a data structure representing what to do） 真正執行這段AST（run）時，它會以尾遞歸（源碼resume方法）的形式執行/解開這段AST，是前面CPS的升級版(其實也是上面手寫TCO的一種方式： Tail Call Elimination in Scala Monads)，也就是說Trampoline就是將函數非尾遞歸調用轉變成了尾遞歸調用。
這也是一種以堆空間換取棧空間的做法，被稱為Stackless Scala，這是對非尾遞歸函數優化的通用解（非編譯器層面）。我倒不覺得一定要寫出尾遞歸版本，代碼語義清晰最重要，一般寫出遞歸函數，都是針對嵌套/遞歸/歸納定義的數據結構，不見得都能寫出（能被應用TCO的）尾遞歸的形式，並且嵌套深度有限制（太深則stack overflow）不見得是壞事（逃；能優化成循環/非溢出的尾遞歸函數使用場合大都是迭代，此時也可以用別的方法去解決比如Stream：val fibs: Stream[Int] = 0 #:: 1 #:: fibs.zip(fibs.tail).map { n =&> n._1 + n._2 }
println(fibs.drop(10).head)
就懂這麼多了。。。
------------------------------------tail-call tail-rec: http://web.archive.org/web/20111030134120/http://www.sidhe.org/~dan/blog/archives/000211.html在設計的時候，可以先寫出循環版本，再把循環中所用到的局部變數都變成遞歸函數的參數。這是實際開發中常用的一種辦法。
可以參考我這篇文章：知乎專欄
例如，我們寫一個函數，計算m的n次方，使用循環，就寫成這樣：public static double power1(double m, int n) {
double result = 1.0;
double t = m;
for (int i = 1; i &<= n; i &<&<= 1) {
if ((n i) &> 0)
result *= t;
t *= t;
}
return resu<
}
把這個函數里用到的result, i, t 這三個局部變數變成遞歸函數的參數，我們可以直接進行轉換：
def pow_helper(n : Int, r : Double, t : Double, i : Int) : Double = {
if (n &< i) {
r
}
else {
if ((n i) &> 0)
pow_helper(n, r * t, t * t, i &<&< 1);
else
pow_helper(n, r, t * t, i &<&< 1);
}
}
def pow_2(m : Double, n : Int) : Double = {
return pow_helper(n, 1.0, m, 1);
}
可以看到，result, i, t 這三個變數並沒有消失，邏輯也沒有發生任何變化，但是形式已經是尾遞歸形式了。這是一種在實際開發中比較實用的技巧。
專欄文章里還有更簡潔的寫法。遇到循環改寫尾遞歸的時候，先寫一個基礎版本，再看能不能更簡潔一點。我一般都是這麼乾的。推薦閱讀：