时间戳

首页 > 解决方案 > 迭代中递归模式的更多技术

recursion - 迭代中递归模式的更多技术

问题描述

建立在 Rust 中将递归函数转换为迭代器的技术？，我想探索迭代器的挑战。

让我们考虑一个基于收益率的递归函数，它的控制流稍微复杂一些：

function one_level(state, depth, max_depth) {
  if depth == max_depth {
    return
  }
  if external_condition(state) {                 // location-1
     for s in next_states_from(state) {          // loop-1
       yield state_to_value(s);
       yield one_level(s, depth+1, max_depth); 
     }
  } else {
     for s in other_next_state_from(state) {     // loop-2
       yield one_level(s, depth+1, max_depth)    // location-2
     }
  }
}

事情变得有趣了，因为有：

在 Rust 迭代器中管理所有这些，我发现自己基本上用属性来装饰我的状态对象，location_1_reached:bool这样我就可以在返回之前在我的next()函数中设置这些。然后我需要在我的代码中乱扔检查，看看我们上次通过这个堆栈帧的状态走了多远。同样，我正在努力以一种干净的方式处理这个问题。

我对建议最感兴趣。作为我正在经历的痛苦的暗示，这是我今天为使其工作而定义的那种结构：

struct MyIteratorStackFrame<'a> {
    arg_1: usize,
    arg_2: Point,
    loop_1_values: Box<dyn Iterator<Item = &'a State> + 'a>,
    loop_2_values: Box<dyn Iterator<Item = &'a State> + 'a>,
    location_1_reached: bool,
    location_2_reached: bool
}

struct MyIterator<'a> {
    max_depth: usize,
    stack: Vec<MyIteratorStackFrame<'a>>,
}

标签： recursionrustiteratoriterationstate

解决方案

您正在谈论的模式是“状态机”，最好使用枚举在 Rust 中表示：

enum Frame {
    NextStates(NextStatesIterator, State),
    OtherStates(OtherStatesIterator)
}
struct Iterator {
    stack: Vec<Frame>, 
}

推荐阅读