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?

• Stargateur: map() isn't necessary.
• Stargateur: 0 is not necessary, std::num::NonZeroUsize will save you space
• Armando Pérez Marqués: @Stargateur My bad, that map() call is leftover code from a previous version of the code. Interestingly, Clippy completely overlooks the useless map().
• Shepmaster: Clippy completely overlooks the useless map() — there are actually times where map(|x| x) isn't a no-op, surprisingly.
• Armando Pérez Marqués: @Shepmaster Can you expand more on which cases map(|x| x) is useful or not? Or does it deserves a full question in StackOverflow?

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;
 }
 }
}

• Armando Pérez Marqués: Thanks! I still not familiar with what (functions/structs/traits/imports?) can be nested inside functions/blocks in Rust, is it all the same, and it only affects visibility? But yeah, the "shim" function is how I would do it in general (I also know it as a "portal" function).
• Armando Pérez Marqués: Of course (at least regarding Fibonacci) recursion is not great, I just wanted to learn more about Rust (and memory/references) using that constraint. Thanks so much for the links!

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