时间戳

首页 > 解决方案 > 是否可以在 DFS 的递归求解问题中来回移动迭代器？

recursion - 是否可以在 DFS 的递归求解问题中来回移动迭代器？

问题描述

假设我有迭代器let itt = some_string.chars().iter();并且我有解析 json 的函数（或某种树搜索）是否可以在该函数的另一个递归调用之间来回移动迭代器？

更简单的例子：


fn f(it: Iter<i32>, level: i32) -> Iter<i32>{
    let mut mit = it;
    for num in mit {
        if level > 2 {
            println!("{} {}", level, num);
            break
        }
        println!("{} {}", level, num);
        mit = f(&mit, level+1);
    }
    mit
}

fn main() {
    let tab = [1,2,3,4,5];
    let mut itr = tab.iter();
    f(itr, 1);
}

预期输出：

1 1
2 2 
3 3
2 4 
3 5

顺便说一句，这个例子不起作用并且使它起作用（或说明它不是要走的路）将解决这个问题，非常欢迎指向相关的阅读材料

标签： recursionrustiterator

解决方案

您编写的代码根本无法编译，原因有两个。首先，考虑表达式f(&mit, level + 1)。这不进行类型检查，因为f期望它的第一个参数是类型Iter<i32>，但是&mit: &Iter<i32>。因此，您需要将其替换为f(mit, level + 1). 我会解决这个问题。

第二个问题是for循环隐式调用into_iter，mit它移动mit。for只是语法糖，所以我将手动对for-loop 进行脱糖，以向您展示真正发生的事情：

fn f(it: Iter<i32>, level: i32) -> Iter<i32>{
    let mut mit = it;
    let mut iterator = mit.into_iter();
    while let Some(num) = iterator.next() {
        if level > 2 {
            println!("{} {}", level, num);
            break
        }
        println!("{} {}", level, num);
        mit = f(mit, level+1);
    }
    mit
}

因为Iter<i32>没有实现Copy，所以这是一个use-after-move错误。我们mit进入该into_iter方法，但我们再次寻求在计算中使用它f(mit, level + 1)。

请注意，这实际上非常重要。通过以这种方式设置for-loops，Rust 可以防止您在迭代集合时以不好的方式改变集合，这可能导致意外结果（在某些情况下甚至可能出现未定义的行为）。

值得庆幸的是，既然我们知道了脱糖代码的样子，修复这个错误就很容易了。我们只是在脱糖代码中完全摆脱了变量iterator并得到以下内容：

fn f(it: Iter<i32>, level: i32) -> Iter<i32>{
    let mut mit = it;
    while let Some(num) = mit.next() {
        if level > 2 {
            println!("{} {}", level, num);
            break
        }
        println!("{} {}", level, num);
        mit = f(mit, level+1);
    }
    mit
}

这是因为对于 type Iter<T>，该方法into_iter()只返回Iter<T>自身。

这将打印预期的输出。

1 1
2 2
3 3
2 4
3 5

按要求。

编辑：

在您的特定情况下，我们可以按如下方式重写您的代码：

fn f(it: Iter<i32>, mut level: i32) {
    for num in it {
        println!("{} {}", level, num);
        level = if level > 2 { level - 1 } else { level + 1 };
    }
}

fn main() {
    let tab = [1,2,3,4,5];
    let itr = tab.iter();
    f(itr, 1);
}

这完全消除了递归。

推荐阅读