[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) } ```