Recursive Fibonacci in Rust with memoization

Question

I'm trying to come up with an "elegant" way of calculating Fibonacci for number in Rust, using recursion and memoization (self-imposed requirements).

This is what I have so far:

fn fib(n: usize, memo: &mut [Option<usize>]) -> usize {
    memo[n].map(|v| v).unwrap_or_else(|| {
        let result = {
            if n > 1 {
                fib(n - 1, memo) + fib(n - 2, memo)
            } else {
                1
            }
        };
        memo[n] = Some(result);
        result
    })
}

fn main() {
    let number = 46;
    let mut memo: Vec<Option<usize>> = vec![None; number + 1];
    println!("{}", fib(number, &mut memo));
}

My cache in this implementation is just a slice of optional values, if the position contains Some(x) that's a cache hit, otherwise, in a closure, compute the value, passing the cache along, and just before returning the value save it as a Some(v) in the cache.

I figured that setting up a cache this way would make writes faster, since the memory is already allocated.

Can it be made faster? Or cleaner/more readable?

Answer 1

1. There's no reason to ascribe a type to memo.
2. Don't expose the memoization logic outside the call. Instead, create a shim function that creates the memoization vector for you.
3. You can then define the memoized function inside the shim function, preventing people from accidentally calling it.
4. Since the memo variable isn't used after the top-most recursive call, you can just pass in the reference directly, without creating a variable.
5. As mentioned in the comments, the map(|x| x) call is not needed here.
6. Write some kind of automated tests.

fn fib(number: usize) -> usize {
    fn fib_memo(n: usize, memo: &mut [Option<usize>]) -> usize {
        memo[n].unwrap_or_else(|| {
            let result = {
                if n > 1 {
                    fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
                } else {
                    1
                }
            };
            memo[n] = Some(result);
            result
        })
    }

    fib_memo(number, &mut vec![None; number + 1])
}

fn main() {
    let number = 46;
    let r = fib(number);
    println!("{}", r);
    assert_eq!(2971215073, r);
}

That being said, I'd point out that this memoized version of Fibonacci is not the most efficient — you don't need to keep every previous value forever. Instead, check out numerous ways of being more efficient:

• Implement a generic Fibonacci sequence in Rust without using Copy trait
• How to swap two variables?
• How to avoid excessive cloning in Rust?
• Is it possible to use a fold with a Vec?

One possible implementation of that:

fn fib(n: usize) -> usize {
    fn fib_memo(n: usize, memo: &mut [usize; 2]) -> usize {
        let [a, b] = *memo;
        let c = a + b;
        if n == 0 {
            c
        } else {
            *memo = [b, c];
            fib_memo(n - 1, memo)
        }
    }

    if n < 2 {
        1
    } else {
        fib_memo(n - 2, &mut [1, 1])
    }
}

Or a non-recursive variant:

fn fib(n: usize) -> usize {
    if n < 2 {
        1
    } else {
        let mut memo = [1, 1];
        let mut n = n - 2;

        loop {
            let [a, b] = memo;
            let c = a + b;

            if n == 0 {
                return c;
            }

            memo = [b, c];
            n -= 1;
        }
    }
}

Answer 2

This is probably way late already. But I sort of preferred handling a memoized solution to fibonacci in rust using the hashMap.

pub fn memoized_fib(num: usize) -> usize {
    struct Fibi {
        memo: HashMap<usize, usize>,
    }

    impl Fibi {
        fn new(num: usize) -> Fibi {
            return Fibi {
                memo: HashMap::with_capacity(num),
            };
        }

        fn get_fibi(&mut self, num: usize) -> usize {
            if num <= 2 {
                return 1;
            }

            if !self.memo.contains_key(&num) {
                let fibi_one = self.get_fibi(num - 1);
                let fibi_two = self.get_fibi(num - 2);

                self.memo.entry(num).or_insert(fibi_one + fibi_two);
            }
            return *self.memo.get(&num).unwrap();
        }
    }

    let mut result = Fibi::new(num);
    return result.get_fibi(num);
}