Rust：在递归函数中使用可变引用

Question

我正在尝试使用像这样的递归函数打印 Vec 的唯一连续子数组：

use std::collections::HashSet;

fn recurse<'a>(nums: &'a [i32], already_printed: &'a mut HashSet<&'a [i32]>) {
    if !already_printed.contains(nums) {
        println!("{:#?}", nums);
    }

    already_printed.insert(nums);

    if nums.len() >= 2 {
        recurse(&nums[0..nums.len() - 1], already_printed);
        recurse(&nums[1..nums.len()], already_printed);
    }
}

pub fn main() {
    let k = vec![1, 2, 3, 4, 5];
    let mut already_printed: HashSet<&[i32]> = HashSet::new();
    recurse(&k[0..], &mut already_printed);
}

这当然，正如有经验的 Rustaceans 可能已经猜到的那样，编译失败并出现以下错误：

error[E0499]: cannot borrow `*already_printed` as mutable more than once at a time
  --> src/main.rs:12:39
   |
3  | fn recurse<'a>(nums: &'a [i32], already_printed: &'a mut HashSet<&'a [i32]>) {
   |            -- lifetime `'a` defined here
...
11 |         recurse(&nums[0..nums.len() - 1], already_printed);
   |         --------------------------------------------------
   |         |                                 |
   |         |                                 first mutable borrow occurs here
   |         argument requires that `*already_printed` is borrowed for `'a`
12 |         recurse(&nums[1..nums.len()], already_printed);
   |                                       ^^^^^^^^^^^^^^^ second mutable borrow occurs here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0499`.

我从非常有用的错误中了解到 为什么 编译器拒绝编译它。但是，一般来说，实现采用上述代码中所示的可变引用的递归函数的解决方法是什么？

我能想到的一种可能的解决方法是使用 内部可变性模式 à la RefCell:

use std::cell::RefCell;
use std::collections::HashSet;

fn recurse<'a>(nums: &'a [i32], already_printed: &'a RefCell<HashSet<&'a [i32]>>) {
    if !already_printed.borrow().contains(nums) {
        println!("{:#?}", nums);
    }

    already_printed.borrow_mut().insert(nums);

    if nums.len() >= 2 {
        recurse(&nums[0..nums.len() - 1], already_printed);
        recurse(&nums[1..nums.len()], already_printed);
    }
}

pub fn main() {
    let k = vec![1, 2, 3, 4, 5];
    let already_printed: HashSet<&[i32]> = HashSet::new();
    let ref_cell: RefCell<HashSet<&[i32]>> = RefCell::new(already_printed);
    recurse(&k[0..], &ref_cell);
}

虽然这可行，但这似乎放弃了编译时借用检查器提供的安全性 rails。是否有不同的规范方法来进行如上所述的递归函数调用，同时仍然有编译时间借用检查器通过？

Answer 1

神奇的解决办法就是把函数的声明改成

fn recurse<'a, 'b>(nums: &'a [i32], already_printed: &'b mut HashSet<&'a [i32]>) {
// I just changed this lifetime -----------------------^

你的算法不工作没有深层原因，除了你在没有理由的情况下添加了太多约束。

当您从 recurse 内部调用 recurse 时，完全没问题，因为它会在调用结束时释放所有权。所以它必须有效。

但是您要求所有生命周期都相同，而您可以让编译器确定真正的约束。

Rust：在递归函数中使用可变引用

Rust: Use of Mutable References in Recursive Function

recursion

rust

borrow-checker