recursion - 如何在递归调用中使用迭代器来改变数据序列？

Question

TL/DR

我有一个递归算法，每个调用都想修改可迭代数据结构（a Vec）中的条目。如何使用迭代器在 Rust 中正确建模？

免责声明

问题出现在一个不同的、更复杂的环境中，我试图建立一个相当小的例子来突出这个问题。我提到这一点是为了解释，如果您针对我在下面的代码中解决的特定问题（即子集总和）推荐一个完全不同的解决方案，这对我没有帮助。

例子

考虑以下代码，并删除任一选项前面的单个斜杠以将其注释掉。现在，选项 1 编译并按预期工作，但选项 2 不编译。

#[derive(Clone, Copy)]
struct Item {
    in_subset: bool,
    value: u32,
}

fn try_find_subset_with_sum(items: &mut Vec<Item>, goal: u32) -> bool {
    let current = items
        .iter()
        .filter(|x| x.in_subset)
        .fold(0, |sum, x| sum + x.value);
    if current == goal {
        true
    } else {
        if current > goal {
            false
        } else {
            //* OPTION 1: ********************************
            for k in 0..items.len() {
                if !items[k].in_subset {
                    items[k].in_subset = true;
                    if try_find_subset_with_sum(items, goal) {
                        return true;
                    }
                    items[k].in_subset = false;
                }
            }
            // *******************************************/
            //* OPTION 2: ********************************
            for x in items.iter_mut() {
                if !x.in_subset {
                    x.in_subset = true;
                    if try_find_subset_with_sum(items, goal) {
                        return true;
                    } else {
                        x.in_subset = false
                    }
                }
            }
            // *******************************************/
            false
        }
    }
}

fn main() {
    let tmp = vec![12, 9, 2, 1, 13, 46, 5, 5, 9];
    let mut set: Vec<Item> = tmp
        .into_iter()
        .map(|x| Item {
            in_subset: false,
            value: x,
        })
        .collect();
    if try_find_subset_with_sum(&mut set, 16) {
        println!("found the following subset:");
        for x in set {
            if x.in_subset {
                println!("{}", x.value);
            }
        }
    }
}

选项 2 的错误消息指出：

error[E0499]: cannot borrow `*items` as mutable more than once at a time
  --> src/main.rs:33:49
   |
30 |             for x in items.iter_mut() {
   |                      ----------------
   |                      |
   |                      first mutable borrow occurs here
   |                      first borrow used here, in later iteration of loop
...
33 |                     if try_find_subset_with_sum(items, goal) {
   |                                                 ^^^^^ second mutable borrow occurs here

我明白编译器在告诉我什么。如果它是人类，我会回骂它“只要我修改数据时借用该死的可迭代，并在递归调用大声喊叫之前将其取回！” - 但我明白它可能无法做到这一点。

问题

有没有比选项 1 更优雅的方法来解决这个问题？有没有办法用迭代器做到这一点？

标签： recursionrustborrow-checker