Golang斐波那契数列命令式实现与函数式方案对比

Golang斐波那契数列命令式实现与函数式方案对比 命令式代码存在变量修改、副作用，并且总体上在我看来效率不高。以下是更高效的方法：

package main

import "fmt"

func fib(n int) int {
	if n == 0 {
		return 0
	} else if n == 1 {
		return 1
	} else {
		return (fib(n-2) + fib(n-1))
	}
func main() {
	fmt.println(fib(5))
}
13 回复

使用空格。

更多关于Golang斐波那契数列命令式实现与函数式方案对比的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


如何实现代码缩进？除此之外，我的代码是正确的。

哪个更重要？性能还是良好的代码？在我看来，Go 语言速度极快，因此良好的代码更为重要。

Rust 是函数式和命令式编程的混合体，结合了两者的优点，并且 Python 可以通过 Rust 进行优化。

PythonGuyWhoLovesGo:

你是如何计算该算法复杂度的

我没有计算，是其他人计算的，请查看链接。

PythonGuyWhoLovesGo:

可变性从来都不是一件好事

除非最佳性能是件好事。尽管可变性确实会使代码更难推理，从而难以保证其正确性。

突变并不一定是好的，但它通常是最快、最有效的方式。

所有那些告诉你不可变性的函数式语言，都尽可能地避免复制和重新创建内容，它们将递归重写为进行突变的循环，因为这正是计算机内部的工作方式。

你是如何计算那个算法复杂度的？我读过一些苏兹达尔尼茨基的著作，最终确信函数式范式是最好的范式。我只是想看看一个没有突变和副作用的函数式范式方法。当然我知道这是个糟糕的算法，但突变从来都不是好事。

在 Go 中尝试进行纯函数式编程是与语言设计和哲学背道而驰的。如果纯函数式编程至关重要，那么请使用专为其设计和优化的语言进行工作。也许你应该努力成为热爱 {Haskell, F#, OCaml, Idris, Elm 等} 的 Python 开发者。

如果你打算在Go语言中仅限于使用函数式编程技术，正如@NobbZ所指出的，缺乏尾调用优化（TCO）是一个致命问题（除非采用类似Go中的尾递归的编码方式）。

或者正确复制/粘贴格式良好的代码。

关于代码：

  1. 它在 return 语句后使用了 else，大多数代码检查工具（linter）对此会提出警告。
  2. 它使用了计算斐波那契数列的朴素方法，众所周知这种方法效率低下。
  3. 它不是尾递归的，因此在任何运行时环境中，对于足够大的 n，都会导致栈溢出。
  4. 它是递归的，这会在 Go 语言中导致栈溢出，因为 Go 不会对递归进行任何自动优化，无论是否是尾递归。

虽然存在一些经过优化且仍可证明正确的递归实现，但由于缺少尾调用优化（TCO），我在 Go 中不会使用它们。我只会使用基于循环的方法，该方法会修改一些变量并最终返回结果。

请注意，朴素实现的算法复杂度是 O(1.6ⁿ)，而更优化的版本是 O(n)。因此，通常在算法课程中，你很早就会学习到这些优化版本……

PythonGuyWhoLovesGo:

什么更重要？性能还是良好的代码？在我看来，Go 语言速度极快，所以良好的代码更重要。

答案当然是：视情况而定。有时性能为王，有时可读性可能更重要。建议你抽时间读一下这篇文章。请记住，根据我的经验，Go 语言比大多数其他垃圾回收语言要快得多（其他人也有同样的体验）。现在想象一下，你正在运行一个模拟，需要租用昂贵的硬件时间，而这个模拟需要运行一周。如果你能将性能提高哪怕 10%，你认为这重要吗？

所以，是的，性能很重要。如果性能不重要，Go 语言可能从一开始就不会存在。话虽如此，对于像这样完全人为构造且永远不会投入生产的代码，你可以随意选择。如果不需要，就不要过早地进行优化。

最后，我可能属于少数派，但我认为在这种情况下，命令式方法比使用递归更容易阅读/理解。不过，这只是个人偏好。

这是一个典型的递归实现，但存在几个问题：递归调用会导致指数级的时间复杂度，并且代码中有语法错误。以下是命令式和函数式两种改进方案：

命令式方案（迭代法）

func fibIterative(n int) int {
    if n <= 1 {
        return n
    }
    
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

函数式方案（闭包+记忆化）

func fibFunctional() func(int) int {
    cache := make(map[int]int)
    
    var fib func(int) int
    fib = func(n int) int {
        if n <= 1 {
            return n
        }
        
        if val, ok := cache[n]; ok {
            return val
        }
        
        result := fib(n-1) + fib(n-2)
        cache[n] = result
        return result
    }
    
    return fib
}

// 使用方式
func main() {
    fib := fibFunctional()
    fmt.Println(fib(5))  // 5
    fmt.Println(fib(10)) // 55
}

性能对比

func benchmark() {
    n := 40
    
    // 命令式迭代
    start := time.Now()
    result1 := fibIterative(n)
    elapsed1 := time.Since(start)
    
    // 函数式记忆化
    fibFunc := fibFunctional()
    start = time.Now()
    result2 := fibFunc(n)
    elapsed2 := time.Since(start)
    
    fmt.Printf("迭代法: 结果=%d, 耗时=%v\n", result1, elapsed1)
    fmt.Printf("函数式: 结果=%d, 耗时=%v\n", result2, elapsed2)
}

命令式方案时间复杂度O(n)，空间复杂度O(1)；函数式方案通过记忆化将时间复杂度优化到O(n)，空间复杂度O(n)。对于斐波那契数列计算，命令式迭代法通常更高效，而函数式方案在多次调用相同参数时更有优势。

回到顶部