Rust：递归函数变异向量指南

Question

我需要一些指导如何处理递归函数，该递归函数需要改变从以前的递归级别提供给它的向量。

fn solve (graph: &CompleteGraph) -> Path {
    let mut path = Path { cities: Vec::<usize>::new() };
    let mut visited = Visited { cities: vec!(false; graph.numcities) };
    let since = Instant::now();

    let bestpath = Path { cities: trivialpath(&graph) };
    let besttotal = pathtotal(&bestpath.cities, &graph);

    let (path, visited, bestpath, besttotal) = solverec(path, 0.0, visited, since, bestpath, besttotal);

    return bestpath;
}

fn solverec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, besttotal: f64) -> (Path, Visited, Path, f64) {
    
    if since.elapsed() > Duration::from_secs(5) {
        return (path, visited, bestpath, besttotal);
    }
    if pathtotal > besttotal {
        return (path, visited, bestpath, besttotal);
    }

    for nextcity in 0..visited.cities.len() {
        if visited.cities[nextcity] == false {
            path.cities.push(nextcity);
            visited.cities[nextcity] = true;
            let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, bestpath, besttotal);
            visited.cities[nextcity] = false;
            path.cities.pop();
        }
    }

    unimplemented!();
}

编译器抱怨很多：

error[E0382]: borrow of moved value: `visited`
   --> tsp-arekbulski-05-brute.rs:123:6
    |
113 | ...verec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, best...
    |                                       ------- move occurs because `visited` has type `Visited`, which does not implement the `Copy` trait
...
123 | ...isited.cities[nextcity] == false {
    |         ^^^^^^^^^^^^^^ value borrowed here after move
...
126 | ... (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, bestpat...
    |                                                                               ------- value moved here, in previous iteration of loop

error[E0596]: cannot borrow `path.cities` as mutable, as `path` is not declared as mutable
   --> tsp-arekbulski-05-brute.rs:124:4
    |
113 | fn solverec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, b...
    |              ---- help: consider changing this to be mutable: `mut path`
...
124 |             path.cities.push(nextcity);
    |             ^^^^^^^^^^^ cannot borrow as mutable

error[E0382]: borrow of moved value: `path`
   --> tsp-arekbulski-05-brute.rs:124:4
    |
113 | fn solverec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, b...
    |              ---- move occurs because `path` has type `Path`, which does not implement the `Copy` trait
...
124 |             path.cities.push(nextcity);
    |             ^^^^^^^^^^^ value borrowed here after move
125 |             visited.cities[nextcity] = true;
126 |             let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, best...
    |                                                                 ---- value moved here, in previous iteration of loop

error[E0596]: cannot borrow `visited.cities` as mutable, as `visited` is not declared as mutable
   --> tsp-arekbulski-05-brute.rs:125:4
    |
113 | fn solverec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, b...
    |                                          ------- help: consider changing this to be mutable: `mut visited`
...
125 |             visited.cities[nextcity] = true;
    |             ^^^^^^^^^^^^^^ cannot borrow as mutable

error[E0382]: use of moved value: `bestpath`
   --> tsp-arekbulski-05-brute.rs:126:89
    |
113 | ...sited, since: Instant, bestpath: Path, besttotal: f64) -> (Path, Visited, Path, f64) {
    |                           -------- move occurs because `bestpath` has type `Path`, which does not implement the `Copy` trait
...
126 | ...ec(path, pathtotal, visited, since, bestpath, besttotal);
    |                                                 ^^^^^^^^ value moved here, in previous iteration of loop

error[E0596]: cannot borrow `visited.cities` as mutable, as `visited` is not declared as mutable
   --> tsp-arekbulski-05-brute.rs:127:4
    |
126 |             let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, best...
    |                        ------- help: consider changing this to be mutable: `mut visited`
127 |             visited.cities[nextcity] = false;
    |             ^^^^^^^^^^^^^^ cannot borrow as mutable

error[E0596]: cannot borrow `path.cities` as mutable, as `path` is not declared as mutable
   --> tsp-arekbulski-05-brute.rs:128:4
    |
126 |             let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, best...
    |                  ---- help: consider changing this to be mutable: `mut path`
127 |             visited.cities[nextcity] = false;
128 |             path.cities.pop();
    |             ^^^^^^^^^^^ cannot borrow as mutable

error: aborting due to 7 previous errors; 7 warnings emitted

Answer 1

        let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, bestpath, besttotal);

这会消耗 4 个函数局部变量，并用 4 个 loop-local 变量隐藏它们。

所以循环只能执行一次，之后就没什么用了：循环局部变量被丢弃在循环结束时。

您可能曾尝试使用它，因为批量重新分配

(path, visited, bestpath, besttotal) = ...

没用。

遗憾的是，不，它不是，重新分配不是模式，所以你不能使用解构重新分配，没有重新声明不能解决它。您必须进行函数局部绑定 mut，然后根据从 solverec 获得的循环局部结果显式重新分配，例如

fn solverec (mut path: Path, mut pathtotal: f64, mut visited: Visited, mut since: Instant, mut bestpath: Path, mut besttotal: f64) -> (Path, Visited, Path, f64) {
    // ...
        let r = solverec(path, pathtotal, visited, since, bestpath, besttotal);
        path = r.0;
        visited = r.1;
        bestpath = r.2;
        besttotal = r.3;

我建议要么将它们提取到单个结构（可能只是一个 typedef，例如 type Solution = (Path, Visited, Path, f64)），这样它们就可以作为一个单元而不是零散地进行操作或重新分配，或者以某种方式重组整个结构。

Rust：递归函数变异向量指南

Rust: guidance on recursive function mutating vectors

arrays

recursion

rust

borrow-checker