# Recursive Fibonacci in Rust with memoization

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.

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

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:

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

• 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 Sep 29 '18 at 18:26
• 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! – Armando Pérez Marqués Sep 29 '18 at 18:31

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