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

Question

I created the following simple Fibonacci implementations:

#![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
        }
    }
}

I created them to try cargo bench, so I wrote the following tests:

#[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)
        });
    }
}

I know that a recursive implementation is usually slower than an urgent one, especially since Rust does not support tail recursion optimization (which this implementation could not use in any case). But I did not expect the following difference almost 2,000 times:

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)

I ran it on both Windows and Ubuntu with the latest Rust ( rustc 1.25.0-nightly) nightly compiler and got similar results.

Is this speed difference normal? Did I write something "wrong"? Or are my tests wrong?

Answer 1

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).

Answer 2

:

• : O (N),
• : O (1.6 ^N).

20 (N) 12089 (1.6 ^N), , .

. .

. , , .