Why do I not need to explicitly lend a borrowed, m

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:

In main, let mut cache means "I want to be able to mutate this hashmap (or re-assign the variable)".
When main calls fib, it passes &mut cache to say "I'm lending you this, and you're allowed to mutate it."
In the signature of fib, cache: &mut Hashmap means "I expect to be lent a mutable HashMap - to borrow it with permission to mutate"

(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?

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>.