Return to Revisions

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