在递归算法和事件驱动的使用者之间进行协调的模式

Question

考虑这个经典的递归伪代码解决方案来解决河内塔问题：

  void move(num,src,dest,spare) {
      if(num == 1) {
         moveSingle(src,dest);
      } else {
         move(num-1,src,spare,dest);
         move(1,src,dest,spare);
         move(num-1,spare,dest,src);
      }
  }

。并考虑显示引擎中的事件循环，例如处理

  void draw() {
      // code to draw a single frame goes here; for example
      if(! aDiscIsInMotion()) {
          getNextMove();
      }
      updateCoordinates();
      drawMovingDisc();
  }

两者之间有什么模式需要协调？

我想到了两个选项：

线程和队列

moveSingle（） 将移动写入 FIFO 队列。如果队列已满负荷，这可能会阻塞。getNextMove（） 从队列中读取移动。

我确定这工作正常，但我很好奇是否有一种模式可以避免线程。

使用显式堆栈而不是递归

重写递归算法以在堆中使用 LIFO 队列，而不是调用堆栈。像这样：

 Move getMove() {
     if(lifo.isEmpty()) {
         return null;
     }
     State state = lifo.pop();
     while(state.num != 1) {
         lifo.push(new State(state.num -1, state.spare, state.dest, state.src));
         lifo.push(new State(1, state.src, state.dest, state.spare));
         lifo.push(new State(state.num -1, state.src, state.spare, state.dest));
         state = lifo.pop();
     }
     return new Move(state); // guaranteed num==1
 }

。同样，这是有效的，但我们失去了使用调用堆栈来保留状态的递归的表达能力。

还有没有我没发现的另一种技术？

请注意，尽管我选择了河内塔和处理的示例，但这旨在作为将递归算法与另一个想要轮询更新的接口集成的一般问题。所以我对"你不需要堆栈来解决河内问题"这样的答案不感兴趣——我知道这一点。

Answer 1

你要找的是协程，尽管它们在某些语言（例如Java）中缺失。协程允许您在生成例程实际完成之前屈服于调用例程。我知道有一个 Java 库可以重写字节码以支持协程;如果你的目标是Java，你必须研究它。

您提到的两个变体本质上是替代方案：多线程或排队您想要生成的中间结果。在您的特定情况下，您的算法中没有交互，因此您实际上可以提前创建整个队列，而不是在算法内部进行检查。

编辑：我不确定递归是否有效;我的知识更具理论性。我认为您应该能够直接或通过在递归调用中额外产生多个级别，不过，您应该能够产生多个级别