recursion - 在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>>，以反射(reflect)在调用堆栈每个级别上 next_states_from返回的数据。然后，对于每个 next()调用，请仔细弹出一部分以恢复状态。我觉得我可能会缺少一些东西。

Answer 1

您正在状态图上执行(深度受限)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()，否则您将需要一个临时的)