递归和尾递归
最后更新于：2022-04-02 04:10:46
[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)
}
```
';