V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
zedpass
V2EX  ›  Go 编程语言

关于 Go 递归性能的疑问

  •  
  •   zedpass · 25 天前 · 652 次点击

    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
    }
    
    4 条回复
    Leviathann
        1
    Leviathann  
       25 天前   ❤️ 1
    尾递归没有优化,是说依然有那么深的 callstack ,其他就几乎和迭代法一致

    原始的递归方法慢,是因为有大量重复计算的问题
    everfly
        2
    everfly  
       25 天前   ❤️ 1
    你这两种算法的复杂度都不一样。
    PTLin
        3
    PTLin  
       25 天前   ❤️ 1
    你这一个自顶而下的 dp 算法和一个自底而上的版本比性能,你居然还会对速度有疑问,你这完全就是 dp 没学好。
    archxm
        4
    archxm  
       25 天前   ❤️ 1
    dp 动态规划,会缓存结果的。用啥语言都一样。
    其实学生不必在意性能问题。实际工作,跑一跑,就知道了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1187 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:30 · PVG 07:30 · LAX 16:30 · JFK 19:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.