为什么我的递归 Fibonacci 实施与迭代实施相比如此缓慢？

Question

我创建了以下简单的斐波那契实现：

#![feature(test)]
extern crate test;

pub fn fibonacci_recursive(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        _ => fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
    }
}

pub fn fibonacci_imperative(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        _ => {
            let mut penultimate;
            let mut last = 1;
            let mut fib = 0;
            for _ in 0..n {
                penultimate = last;
                last = fib;
                fib = penultimate + last;
            }
            fib
        }
    }
}

我创建它们是为了试用 cargo bench，所以我编写了以下基准：

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn bench_fibonacci_recursive(b: &mut Bencher) {
        b.iter(|| {
            let n = test::black_box(20);
            fibonacci_recursive(n)
        });
    }

    #[bench]
    fn bench_fibonacci_imperative(b: &mut Bencher) {
        b.iter(|| {
            let n = test::black_box(20);
            fibonacci_imperative(n)
        });
    }
}

我知道递归实现通常比命令式实现慢，特别是因为 Rust 不支持尾递归优化（这个实现无论如何都不能使用）。但是没想到下面差了将近2000倍：

running 2 tests
test tests::bench_fibonacci_imperative ... bench:          15 ns/iter (+/- 3)
test tests::bench_fibonacci_recursive  ... bench:      28,435 ns/iter (+/- 1,114)

我运行在 Windows 和 Ubuntu 上使用最新的 Rust nightly 编译器 (rustc 1.25.0-nightly) 并获得了相似的结果。

这种速度差异正常吗？我是不是写了什么"wrong"？还是我的基准有缺陷？

Answer 1

两种实现的算法复杂度不同：

您的迭代实现使用累加器：O(N)，
你的递归实现不是：O(1.6^N).

由于20(N) << 12089(1.6^N)，相差较大很正常

请参阅 this answer 以了解在简单实施情况下复杂度的精确计算。

注意：您在迭代案例中使用的方法称为 dynamic programming。

Answer 2

正如 Shepmaster 所说，您应该使用累加器来保留之前计算的 fib(n - 1) 和 fib(n - 2) 否则您将继续计算相同的值：

pub fn fibonacci_recursive(n: u32) -> u32 {
    fn inner(n: u32, penultimate: u32, last: u32) -> u32 {
        match n {
            0 => penultimate,
            1 => last,
            _ => inner(n - 1, last, penultimate + last),
        }
    }
    inner(n, 0, 1)
}

fn main() {
    assert_eq!(fibonacci_recursive(0), 0);
    assert_eq!(fibonacci_recursive(1), 1);
    assert_eq!(fibonacci_recursive(2), 1);
    assert_eq!(fibonacci_recursive(20), 6765);
}

last 等同于 fib(n - 1).
penultimate 等同于 fib(n - 2)。

为什么我的递归 Fibonacci 实施与迭代实施相比如此缓慢？

Why is my recursive Fibonacci implementation so slow compared to an iterative one?

recursion

performance

benchmarking

rust