How do I recursively pass a mutable reference?

Question

I am attempting to solve this problem in Rust.

Here is my non-compiling Rust code:

use std::collections::HashMap;

fn main() {
    // initialize HashMap
    let mut fibs: HashMap<u32, u32> = HashMap::new();
    fibs.insert(0, 1);
    fibs.insert(1, 1);
    let mut n = 1;
    let mut sum = 0;
    while fib(n, &mut fibs) < 4000000 {
        sum += if fib(n, &mut fibs) % 2 == 0 {
            fib(n, &mut fibs)
        } else {
            0
        };
        n += 1;
    }
    println!("{}", sum);
}

fn fib(n: u32, fibs: &mut HashMap<u32, u32>) -> u32 {
    if !fibs.contains_key(&n) {
        fibs.insert(n, fib(n - 1, &mut fibs) + fib(n - 2, &mut fibs));
    }
    *fibs.get(&n).unwrap()
}

error[E0596]: cannot borrow `fibs` as mutable, as it is not declared as mutable
  --> src/main.rs:22:35
   |
20 | fn fib(n: u32, fibs: &mut HashMap<u32, u32>) -> u32 {
   |                ---- help: consider changing this to be mutable: `mut fibs`
21 |     if !fibs.contains_key(&n) {
22 |         fibs.insert(n, fib(n - 1, &mut fibs) + fib(n - 2, &mut fibs));
   |                                   ^^^^^^^^^ cannot borrow as mutable

error[E0499]: cannot borrow `fibs` as mutable more than once at a time
  --> src/main.rs:22:35
   |
22 |         fibs.insert(n, fib(n - 1, &mut fibs) + fib(n - 2, &mut fibs));
   |         ---- ------               ^^^^^^^^^ second mutable borrow occurs here
   |         |    |
   |         |    first borrow later used by call
   |         first mutable borrow occurs here

error[E0596]: cannot borrow `fibs` as mutable, as it is not declared as mutable
  --> src/main.rs:22:59
   |
20 | fn fib(n: u32, fibs: &mut HashMap<u32, u32>) -> u32 {
   |                ---- help: consider changing this to be mutable: `mut fibs`
21 |     if !fibs.contains_key(&n) {
22 |         fibs.insert(n, fib(n - 1, &mut fibs) + fib(n - 2, &mut fibs));
   |                                                           ^^^^^^^^^ cannot borrow as mutable

error[E0499]: cannot borrow `fibs` as mutable more than once at a time
  --> src/main.rs:22:59
   |
22 |         fibs.insert(n, fib(n - 1, &mut fibs) + fib(n - 2, &mut fibs));
   |         ---- ------ first borrow later used by call       ^^^^^^^^^ second mutable borrow occurs here
   |         |
   |         first mutable borrow occurs here

The Rust to Python3 translation looks like this:

def main():
    fibs = {}
    fibs[0] = 1
    fibs[1] = 1
    n = 1
    summ = 0
    while fib(n, fibs) < 4000000:
        summ += fib(n, fibs) if fib(n, fibs) % 2 == 0 else 0
        n+=1
    print(summ)
    print(fibs)
def fib(n, fibs):
    if n not in fibs:
        fibs[n] = fib(n-1, fibs) + fib(n-2, fibs)
    return fibs[n]
main()

I understand that this particular implementation is not ideal, but I am solely trying to learn the language. I am trying to only pass a reference of the hashmap to the function. Without changing the approach to solving this problem, how can I use mutable HashMap references, if it's even possible?

Answer 1

fn fib(n: u32, fibs: &mut HashMap<u32, u32>) -> u32 {

fibs is already a mutable reference. In the function, you say &mut fibs, which would get a mutable reference to a mutable reference. That's not useful, and doesn't match the correct type. Instead, pass fibs directly.

Then you have to split out the two child calls:

fn fib(n: u32, fibs: &mut HashMap<u32, u32>) -> u32 {
    if !fibs.contains_key(&n) {
        let a = fib(n - 1, fibs);
        let b = fib(n - 2, fibs);
        fibs.insert(n, a + b);
    }
    *fibs.get(&n).unwrap()
}

This last bit is a limitation of the borrow checker — nested method calls with &mut receivers result in borrowing errors, but separating them into separate statements fixes the issue.

---

As delnan points out:

While taking a mutable reference to a mutable reference is not useful and demonstrates some confusion, it is usually not a type error, since deref coercions can turn &mut &mut T into &mut T, at least when the compiler knows that &mut T is expected.

This is reflected in what the compiler error messages say:

error[E0596]: cannot borrow `fibs` as mutable, as it is not declared as mutable
  --> src/main.rs:22:35
   |
20 | fn fib(n: u32, fibs: &mut HashMap<u32, u32>) -> u32 {
   |                ---- help: consider changing this to be mutable: `mut fibs`
21 |     if !fibs.contains_key(&n) {
22 |         fibs.insert(n, fib(n - 1, &mut fibs) + fib(n - 2, &mut fibs));
   |                                   ^^^^^^^^^ cannot borrow as mutable

Indeed, making the suggested change allows the code to proceed to the next error. However, having nested references like this overcomplicates things, so it's preferred to keep to the appropriate amount of references.