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

我正在努力将一个简单的递归函数变成一个简单的迭代器。问题在于递归函数在其局部变量和调用堆栈中维护状态 - 将其转换为 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()调用，小心地弹出碎片以恢复状态。我觉得我可能错过了一些东西。

您正在执行（深度有限）深度优先搜索 https://en.wikipedia.org/wiki/Depth-first_search在你的状态图上。您可以通过使用单个未处理子树堆栈（取决于您的状态图结构）来迭代地完成此操作。

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()，否则你将需要一个临时的）