CODEWITHSUNDEEP
recursionrustownership
Nathan Long
Nathan Long

Reputation: 125902

Why do I not need to explicitly lend a borrowed, mutable variable?

I've just written a small Rust program which calculates Fibonacci numbers and memoizes the calculation. It works, but I'm a little confused about why, especially the recursive call. (It also probably isn't idiomatic.)

Here's the program:

use std::collections::HashMap;

fn main() {
    let n = 42; // hardcoded for simplicity
    let mut cache = HashMap::new();
    let answer = fib(n, &mut cache);
    println!("fib of {} is {}", n, answer);
}

fn fib(n: i32, cache: &mut HashMap<i32,i32>) -> i32 {
    if cache.contains_key(&n) {
        return cache[&n];
    } else {
        if n < 1 { panic!("must be >= 1") }

        let answer = if n == 1 {
            0
        } else if n == 2 {
            1
        } else {
            fib(n - 1, cache) + fib(n - 2, cache)
        };
        cache.insert(n, answer);
        answer
    }
}

Here's how I understand what's going on:

(Please correct me if I'm wrong.)

But when fib recurses, calling fib(n -1, cache), I do not need to use fib(n -1, &mut cache), and I get an error if I do: "cannot borrow immutable local variable cache as mutable". Huh? It's not an immutable local variable, it's a mutable borrow - right?

If I try fib(n - 1, &cache), I get a slightly different error:

error: mismatched types:
expected `&mut std::collections::hash::map::HashMap<i32, i32>`,
   found `&&mut std::collections::hash::map::HashMap<i32, i32>`

Which looks like it's saying "I expected a mutable reference and got a reference to a mutable reference".

I know that fib is lending in the recursive call because if it gave up ownership, it couldn't call cache.insert afterwards. And I know that this isn't a special case for recursion, because if I define fib2 to be nearly identical to fib, I can have them recurse via each other and it works fine.

Why do I not need to explicitly lend a borrowed, mutable variable?

Upvotes: 11

Views: 1051

Answers (2)

yxx
yxx

Reputation: 1

In your function, cache is a reference of the outside HashMap. And if you still write & mut cache, you are trying to mutate a reference, not the original HashMap.

Upvotes: 0

Snorre
Snorre

Reputation: 486

Your three points are pretty much spot-on. When the compiler won't allow you to pass &mut cache, it is because the value is actually already borrowed. The type of cache is &mut HashMap<i32, i32>, so passing &mut cache results in a value of type &mut &mut HashMap<i32, i32>. Just passing cache results in the expected type.

The specific error message cannot borrow immutable local variable cache as mutable is triggered because the variable cache isn't itself mutable, even though the memory it points to (the HashMap) is. This is because the argument declaration cache: &mut HashMap<i32, i32> doesn't declare a mut variable. This is similar to how a let differs in mutability from a let mut. Rust does support mutable arguments, which in this case would look like mut cache: &mut HashMap<i32, i32>.

Upvotes: 14

Related Questions