OP 是 Go 语言初学者,学到递归这里实现斐波那契数列的计算,看到的资料都说 Go 没有对尾递归做优化,但是我用尾递归的方式测试之后,发现性能会比最原始的递归方式强非常多,这是什么原因呢?
package main
import (
"fmt"
"time"
)
func fibonacciTailRecursive(n int, a int, b int) int {
if n == 0 {
return a
}
return fibonacciTailRecursive(n-1, b, a+b)
}
func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}
func fib1(n int) int {
return fibonacciTailRecursive(n, 0, 1)
}
func main() {
n := 40
start := time.Now()
result := fib(n)
duration := time.Since(start)
fmt.Println(result, duration) // 常规的递归结果 102334155 394.601829ms
start = time.Now()
result = fib1(n)
duration = time.Since(start)
fmt.Println(result, duration) // 使用尾递归结果 102334155 90ns
}
1
Leviathann 25 天前 ![]() 尾递归没有优化,是说依然有那么深的 callstack ,其他就几乎和迭代法一致
原始的递归方法慢,是因为有大量重复计算的问题 |
![]() |
2
everfly 25 天前 ![]() 你这两种算法的复杂度都不一样。
|
![]() |
3
PTLin 25 天前 ![]() 你这一个自顶而下的 dp 算法和一个自底而上的版本比性能,你居然还会对速度有疑问,你这完全就是 dp 没学好。
|
![]() |
4
archxm 25 天前 ![]() dp 动态规划,会缓存结果的。用啥语言都一样。
其实学生不必在意性能问题。实际工作,跑一跑,就知道了。 |