为何我的Julia递归斐波那契代码运行速度远慢于C++？

你编写的Julia递归斐波那契代码及运行结果如下：

function main()

    function Fib(n::Int)
        if (n == 0 || n == 1)
            return n
        end

        return(Fib(n - 2) + Fib(n - 1))
    end

    res = Fib(46)

    println(res)
end

@time main()

运行输出：

1836311903
123.625395 seconds (5.72 M allocations: 88.103 MiB, 0.02% gc time, 0.02% compilation time)

相同逻辑的C++代码仅需约16.5秒，想了解Julia代码慢的原因。

核心原因分析 #

1. 递归实现的固有指数级复杂度 #

递归版斐波那契的时间复杂度是O(2ⁿ)，会重复计算大量子问题（比如计算Fib(46)时，Fib(1)会被计算上百万次）。这种重复计算本身就会导致性能极差，而C++的递归调用开销比Julia更低，所以在这种高频递归场景下，累积的差距会被放大。

2. Julia递归调用的相对开销 #

Julia的函数调用（尤其是递归）开销略高于C++：C是静态编译语言，递归调用的栈操作和参数传递经过编译器深度优化，非常轻量；而Julia是JIT编译的动态语言，即使经过JIT优化，递归调用的底层开销还是比C高一些，在百万级别的递归调用下，这种细微差距会被放大成明显的时间差。

3. 嵌套函数的优化限制 #

你将Fib函数定义在main函数内部，这种嵌套函数的优化空间比全局函数小。Julia的JIT编译器对全局函数的内联、常量传播等优化支持更充分，嵌套函数可能无法获得同等程度的优化，进一步加剧了性能差距。

优化方案 #

方案1：改用迭代实现（最优选择） #

迭代版斐波那契的时间复杂度为O(n)，完全避免重复计算，性能会远超递归版本。示例代码：

function Fib_iter(n::Int)
    n == 0 && return 0
    a, b = 0, 1
    for _ in 2:n
        a, b = b, a + b
    end
    return b
end

function main()
    res = Fib_iter(46)
    println(res)
end

@time main()

此版本在Julia中运行耗时会降到毫秒级，和C++迭代版性能几乎无差距。

方案2：使用记忆化缓存子问题结果 #

通过缓存已经计算过的斐波那契值，避免重复计算，时间复杂度降为O(n)。可以手动用字典实现，或者使用Memoize包：

using Memoize

@memoize function Fib_memo(n::Int)
    n == 0 || n == 1 ? n : Fib_memo(n-2) + Fib_memo(n-1)
end

function main()
    res = Fib_memo(46)
    println(res)
end

@time main()

方案3：将函数改为全局并添加内联提示 #

把Fib移到全局作用域，并添加@inline宏帮助编译器内联调用，减少递归开销：

@inline function Fib(n::Int)
    n == 0 || n == 1 ? n : Fib(n-2) + Fib(n-1)
end

function main()
    res = Fib(46)
    println(res)
end

@time main()

此方案能小幅提升递归版本的性能，但依然无法解决指数级复杂度的根本问题。

内容的提问来源于stack exchange，提问作者AlexGenesis