在 Rust 中将递归函数转换为迭代器的技术？

Question

我正在努力将一个简单的递归函数变成一个简单的迭代器。问题在于递归函数在其局部变量和调用堆栈中维护状态 - 将其转换为 Rust 迭代器意味着基本上将所有函数状态外部化为某些自定义迭代器结构上的可变属性。这是一个相当混乱的尝试。

在像 javascript 或 python 这样的语言中，yield它可以解决这个问题。Rust 中是否有任何技术可以帮助管理这种复杂性？

使用的简单示例yield（伪代码）：

function one_level(state, depth, max_depth) {
  if depth == max_depth {
    return
  }
  for s in next_states_from(state) {
    yield state_to_value(s);
    yield one_level(s, depth+1, max_depth);
  }
}

为了在 Rust 中进行类似的工作，我基本上在迭代器结构上创建一个，以反映调用堆栈的每个级别Vec<Vec<State>>返回的数据。next_states_from然后，对于每次next()调用，小心地将其弹出以恢复状态。我觉得我可能错过了一些东西。

Answer 1

您正在对状态图执行（深度有限的）深度优先搜索。您可以通过使用单个未处理子树堆栈（取决于您的状态图结构）来迭代地完成此操作。

struct Iter {
    stack: Vec<(State, u32)>,
    max_depth: u32,
}

impl Iter {
    fn new(root: State, max_depth: u32) -> Self {
        Self {
            stack: vec![(root, 0)],
            max_depth
        }
    }
}

impl Iterator for Iter {
    type Item = u32; // return type of state_to_value
    fn next(&mut self) -> Option<Self::Item> {
        let (state, depth) = self.stack.pop()?;
        if depth < self.max_depth {
            for s in next_states_from(state) {
                self.stack.push((s, depth+1));
            }
        }
        return Some(state_to_value(state));
    }
}

您的代码有一些细微的差异：

• 迭代器生成根元素的值，而您的版本则不会。这可以很容易地解决使用.skip(1)
• 子级按从右到左的顺序进行处理（与 的结果相反next_states_from）。否则，您将需要反转推送下一个状态的顺序（取决于next_states_from您可以使用的结果类型.rev()，否则您将需要一个临时的）