[TOC] ## 遞歸和尾遞歸概念 遞歸 * 遞歸就是不斷地調用函數本身。 尾遞歸 * 遞歸函數在調用自身后直接傳回其值，而不對其再加運算,函數中所有遞歸形式的調用都出現在函數的末尾 * 尾遞歸函數的特點是在**回歸過程中不用做任何操作**，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼 ### 尾遞歸為何能優化 普通遞歸需要先展開,在計算.展開過稱可以爆棧 ``` function fact(n) { if (n <= 0) { return 1; } else { return n * fact(n - 1); } } //展開 6 * fact(5) 6 * (5 * fact(4)) 6 * (5 * (4 * fact(3)))) // two thousand years later... 6 * (5 * (4 * (3 * (2 * (1 * 1)))))) // <= 最終的展開 //計算 6 * (5 * (4 * (3 * (2 * 1))))) 6 * (5 * (4 * (3 * 2)))) 6 * (5 * (4 * 6))) // two thousand years later... 720 // <= 最終的結果 ``` 尾遞歸優化不會爆棧是因為語言的編譯器或者解釋器所做了“尾遞歸優化”,而不是尾遞歸不會進行展開 ## 階乘 ### 遞歸 ``` package main import "fmt" func Rescuvie(n int) int { if n == 0 { return 1 } return n * Rescuvie(n-1) } func main() { fmt.Println(Rescuvie(5)) } ``` ### 尾遞歸 ``` package main import "fmt" func RescuvieTail(n int, a int) int { if n == 1 { return a } return RescuvieTail(n-1, a*n) } func main() { fmt.Println(RescuvieTail(5, 1)) } ``` ## 斐波那契數列 ### 遞歸 ``` func main() { fmt.Printf("%+v\n", demo(3)) } /** n res cal 1 1 1 2 1 1 3 2 (n-1)*(n-2) */ func demo(n int) int { if n ==1 || n==2 { return 1 }else { return demo(n-1)+ demo(n-2) } } ``` ### 尾遞歸 ``` package main import "fmt" func F(n int, a1, a2 int) int { if n == 0 { return a1 } return F(n-1, a2, a1+a2) } func main() { fmt.Println(F(5, 1, 1)) } ``` ## 二分查找 ``` package main import "fmt" // 二分查找遞歸解法 func BinarySearch(array []int, target int, l, r int) int { if l > r { // 出界了，找不到 return -1 } // 從中間開始找 mid := (l + r) / 2 middleNum := array[mid] if middleNum == target { return mid // 找到了 } else if middleNum > target { // 中間的數比目標還大，從左邊找 return BinarySearch(array, target, 1, mid-1) } else { // 中間的數比目標還小，從右邊找 return BinarySearch(array, target, mid+1, r) } } func main() { array := []int{1, 5, 9, 15, 81, 89, 123, 189, 333} target := 500 result := BinarySearch(array, target, 0, len(array)-1) fmt.Println(target, result) target = 189 result = BinarySearch(array, target, 0, len(array)-1) fmt.Println(target, result) } ```