我刚刚编写了一个小的 Rust 程序,它计算斐波那契数并记录计算结果。它有效,但我对为什么,尤其是递归调用有点困惑。 (它也可能不是惯用的。)
程序如下:
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
}
}
以下是我对发生的事情的理解:
- 在
main
中,let mut cache
表示“我希望能够改变此 hashmap(或重新分配变量)”。 - 当
main
调用fib
时,它通过&mut cache
说“我借给你这个,你可以改变它。” - 在
fib
的签名中,cache: &mut Hashmap
的意思是“我希望被借出一个可变的HashMap——借用它并允许变异”
(如有错误请指正)
但是当fib
递归调用fib(n -1, cache)
时,我不需要使用fib(n -1, &mut cache)
,如果我这样做,我会得到一个错误:“不能借用不可变的局部变量 cache
作为可变的”。嗯?它不是不可变的局部变量,而是可变的借用 - 对吧?
如果我尝试 fib(n - 1, &cache)
,我会得到一个稍微不同的错误:
error: mismatched types:
expected `&mut std::collections::hash::map::HashMap<i32, i32>`,
found `&&mut std::collections::hash::map::HashMap<i32, i32>`
这看起来像是在说“我期待一个可变引用并得到了一个对可变引用的引用”。
我知道 fib
在递归调用中借出,因为如果它放弃所有权,它就不能在之后调用 cache.insert
。而且我知道这不是递归的特例,因为如果我将 fib2
定义为与 fib
几乎相同,我可以让它们相互递归并且它工作正常。
为什么我不需要显式借出一个借用的可变变量?
最佳答案
您的三分非常准确。当编译器不允许您传递 &mut cache
时,因为这个值实际上已经被借用了。 cache
的类型是&mut HashMap<i32, i32>
, 所以路过 &mut cache
结果类型为 &mut &mut HashMap<i32, i32>
.刚好路过cache
结果是预期的类型。
具体错误信息cannot borrow immutable local variable cache as mutable
被触发是因为变量 cache
本身不是可变的,即使它指向的内存(HashMap
)是可变的。这是因为参数声明 cache: &mut HashMap<i32, i32>
没有声明 mut
多变的。这类似于 let
的方式。可变性不同于 let mut
. Rust 确实支持可变参数,在这种情况下它看起来像 mut cache: &mut HashMap<i32, i32>
.
关于recursion - 为什么我不需要显式借出一个借来的可变变量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31502793/