學了一段時間的Go語言了，今天來見識下Go語言寫的遞歸程序。

先來做個經典題題目：

有一對兔子，從出生后第3個月起每個月都生一對兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？

分析：

有以下數學表達式：

Y₁=X₂+X₃ ，Y₂=X₁ ，Y₃=X₂+X₃

Z₁=Y₂+Y₃ ，Z₂=Y₁ ，Z₃=Y₂+Y₃

Z₁+Z₂+Z₃= Y₂+Y₃+Y₁+(Y₂+Y₃)=(Y₂+Y₃+Y₁)+(X₂+X₃+X₁)

因此上面每個月的兔子的數量滿足斐波那契數列。斐波那契數列，那就easy了~~

package mainimport "fmt"func main() {var n float32 = 5result1 := fibonacciRecursively(n)fmt.Println(result1) }//普通遞歸方式 func fibonacciRecursively(n float32) float32 {if n < 3 {return 1}return fibonacciRecursively(n-1) + fibonacciRecursively(n-2) }

嗯，至此，問題就解決了，不過后來發現，還有一種“尾遞歸”的做法。　　

下面換用尾遞歸來實現上面的斐波納契數列：

package mainimport "fmt"func main() {var n float32 = 5result2 := fibonacciTailRecursively(5, 1, 1)fmt.Println(result2) }//尾遞歸方式 func fibonacciTailRecursively(n float32, acc1 float32, acc2 float32) float32 {if n == 1 {return acc1}return fibonacciTailRecursively(n-1, acc2, acc1+acc2) }

使用尾遞歸，速度確實快了很多。

?

————————————————摘自百度百科——————————

尾遞歸是極其重要的，不用尾遞歸，函數的堆棧耗用難以估量，需要保存很多中間函數的堆棧。比如f(n, sum) = f(n-1) + value(n) + sum; 會保存n個函數調用堆棧，而使用尾遞歸f(n, sum) = f(n-1, sum+value(n)); 這樣則只保留后一個函數堆棧即可，之前的可優化刪去。

尾遞歸就是從最后開始計算, 每遞歸一次就算出相應的結果, 也就是說, 函數調用出現在調用者函數的尾部, 因為是尾部, 所以根本沒有必要去保存任何局部變量. 直接讓被調用的函數返回時越過調用者, 返回到調用者的調用者去.

————————————————摘自百度百科———————————

?

再來一個階乘的尾遞歸實現Go語言版：

1 package main 2 3 import "fmt" 4 5 func main() { 6 var n float32 = 6 7 fmt.Println(factorialRecursively(n)) 8 fmt.Println(factorialTailRecursively(n,1)) 9 } 10 11 //普通遞歸 12 func factorialRecursively(n float32) float32 { 13 if n == 1 { 14 return 1 15 } 16 17 return n * factorialRecursively(n-1) 18 } 19 20 //尾遞歸 21 func factorialTailRecursively(n float32, acc float32) float32 { 22 //0！=1，1！=1，所以這里判斷n==0或者n==1都對。 23 if n == 0 { 24 return acc 25 } 26 27 return factorialTailRecursively(n-1, acc*n) 28 }

?

?

?

轉載于:https://www.cnblogs.com/yejg1212/archive/2013/03/30/2991133.html

總結

以上是生活随笔為你收集整理的Go语言学习（七）-----练练笔之递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。