E4b9a6's blog
有善始者实繁，能克终者盖寡。
作者：E4b9a6， 创建：2023-02-26， 字数：2859， 已阅：162， 最后更新：2023-02-26
这篇文章更新于 636 天前，文中部分信息可能失效，请自行甄别无效内容。
递归（Recursion）算法，指一种通过重复将问题分解为相同子问题而解决问题的方法，递归可以实现与循环类似的效果
需要使用递归的场景通常具备以下特征
递归的常见应用如下
递归算法并不常用，在大多数编程语言中其运行效率较低，占用栈空间更大
在递归调用的每一层中都使用了栈存储，递归次数过多易造成栈溢出
例如对于Python语言而言，每进入一个函数调用，都会增加一层栈帧，栈大小不是无限的从而造成栈溢出
数据N的阶乘公式：$n!=n\times(n-1)\times(n-2)...\times1$
代码如下
package main
import (
"fmt"
"time"
)
func Factorial(n int64) int64 {
if n < 2 {
return int64(n)
}
return n * Factorial(n-1)
}
func main() {
var n int64
var number int64 = 1
fmt.Printf("Input n value: ")
fmt.Scan(&n)
var start = time.Now()
result = Factorial(n)
var elapsed = time.Since(start)
fmt.Printf("Factorial %v! result is %v\nTotal times is %v", number, result, elapsed)
}
输出如下
➜ go run main.go
Factorial 25! result is 7034535277573963776
Total times is 298ns
Fibonacci即斐波那契数列，即一个特殊数列（0 1 1 2 3 5 8 ...），特征如下
Go求解斐波那契数列函数如下
package main
import (
"fmt"
"time"
)
func Fibonacci(n int) int {
if n == 1 || n == 2 {
return 1
}
return Fibonacci(n-1) + Fibonacci(n-2)
}
func main() {
var number int = 50
var start = time.Now()
var result int = Fibonacci(number)
var elapsed = time.Since(start)
fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)
}
输出如下
➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 40.354931919s
递归的缺点在开头就已经说过了，因为其重复调用会导致栈溢出，而且在大多数编程语言中递归的效率也不如普通循环
以Fibonacci函数为例，改写为循环
package main
import (
"fmt"
"time"
)
func main() {
var number int = 50
var n1 int = 0
var n2 int = 1
var result int = 0
var start = time.Now()
for n := 2; n <= number; n++ {
result = n1 + n2
n1 = n2
n2 = result
}
var elapsed = time.Since(start)
fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)
}
输出如下
➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 226ns
可以看到时间差距非常明显，这也是递归算法在实际应用中较为劣势的一点
前文提到，对于递归调用而言性能较差的原因是在递归调用的每一层中都使用了栈存储
过多的栈帧占用导致内存占用呈现一个波峰上升的趋势，对递归调用而言，优化其执行效率的思路就是减少其栈帧的产生
在函数编程语言中，语言标准通常会要求编译器或运行平台实现尾调用消除
尾调用 （tail call） 指的是一个函数的最后一条语句也是一个返回调用函数的语句(Wiki)，以Fibonacci为例写一个go语言的尾调用消除例子如下
package main
import (
"fmt"
"time"
)
func Fibonacci(n int, n1 int, n2 int) int {
if n == 0 {
return n1
}
return Fibonacci(n-1, n2, n1+n2)
}
func main() {
var number int = 50
var start = time.Now()
var n1 int = 0
var n2 int = 1
var result int = Fibonacci(number, n1, n2)
var elapsed = time.Since(start)
fmt.Printf("Fibonacci %vth result is %v\nTotal times is %v", number, result, elapsed)
}
➜ go run main.go
Fibonacci 50th result is 12586269025
Total times is 443ns
可以看到，执行效率几乎可以媲美循环写法