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

5 回复

尾递归没有优化,是说依然有那么深的 callstack ,其他就几乎和迭代法一致

原始的递归方法慢,是因为有大量重复计算的问题

更多关于Golang Go语言中关于递归性能的疑问的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


你这两种算法的复杂度都不一样。

你这一个自顶而下的 dp 算法和一个自底而上的版本比性能,你居然还会对速度有疑问,你这完全就是 dp 没学好。

dp 动态规划,会缓存结果的。用啥语言都一样。
其实学生不必在意性能问题。实际工作,跑一跑,就知道了。

在Golang(Go语言)中,递归的性能确实是一个值得关注的话题。递归作为一种常见的编程技巧,通过函数调用自身来解决问题,但在处理大型数据集或深度递归时,可能会遇到性能瓶颈和栈溢出的问题。

首先,递归调用的每次函数调用都会占用一定的栈空间,如果递归深度过大,可能会耗尽栈空间,导致栈溢出错误。此外,频繁的函数调用和返回操作也会增加时间开销,影响程序的性能。

为了提高递归的性能,可以考虑以下几种方法:

  1. 尾递归优化:如果递归函数满足尾递归的条件,编译器可能会进行优化,通过迭代的方式实现递归,从而减少栈空间的使用。不过,Go语言的编译器并不总是对尾递归进行优化,这取决于具体的实现和版本。

  2. 迭代替代递归:在某些情况下,可以使用迭代(循环)来替代递归,从而避免函数调用和返回的开销,以及栈空间的使用。

  3. 增加栈空间:如果确实需要使用深度递归,并且无法通过其他方法优化,可以尝试增加程序的栈空间。这通常涉及到编译器或运行时的设置。

  4. 使用内存池或切片:在处理大型数据集时,可以使用内存池或切片来存储中间结果,从而减少内存分配和回收的开销。

综上所述,虽然递归在Go语言中是一种强大的编程工具,但在使用时需要注意其性能影响,并根据具体情况选择合适的优化方法。

回到顶部