Golang Go语言中关于递归性能的疑问
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
}
Golang Go语言中关于递归性能的疑问
更多关于Golang Go语言中关于递归性能的疑问的实战教程也可以访问 https://www.itying.com/category-94-b0.html
尾递归没有优化,是说依然有那么深的 callstack ,其他就几乎和迭代法一致
原始的递归方法慢,是因为有大量重复计算的问题
更多关于Golang Go语言中关于递归性能的疑问的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html
你这两种算法的复杂度都不一样。
你这一个自顶而下的 dp 算法和一个自底而上的版本比性能,你居然还会对速度有疑问,你这完全就是 dp 没学好。
dp 动态规划,会缓存结果的。用啥语言都一样。
其实学生不必在意性能问题。实际工作,跑一跑,就知道了。
在Golang(Go语言)中,递归的性能确实是一个值得关注的话题。递归作为一种常见的编程技巧,通过函数调用自身来解决问题,但在处理大型数据集或深度递归时,可能会遇到性能瓶颈和栈溢出的问题。
首先,递归调用的每次函数调用都会占用一定的栈空间,如果递归深度过大,可能会耗尽栈空间,导致栈溢出错误。此外,频繁的函数调用和返回操作也会增加时间开销,影响程序的性能。
为了提高递归的性能,可以考虑以下几种方法:
-
尾递归优化:如果递归函数满足尾递归的条件,编译器可能会进行优化,通过迭代的方式实现递归,从而减少栈空间的使用。不过,Go语言的编译器并不总是对尾递归进行优化,这取决于具体的实现和版本。
-
迭代替代递归:在某些情况下,可以使用迭代(循环)来替代递归,从而避免函数调用和返回的开销,以及栈空间的使用。
-
增加栈空间:如果确实需要使用深度递归,并且无法通过其他方法优化,可以尝试增加程序的栈空间。这通常涉及到编译器或运行时的设置。
-
使用内存池或切片:在处理大型数据集时,可以使用内存池或切片来存储中间结果,从而减少内存分配和回收的开销。
综上所述,虽然递归在Go语言中是一种强大的编程工具,但在使用时需要注意其性能影响,并根据具体情况选择合适的优化方法。