递归算法与事件驱动使用者之间的协调模式

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)中缺失。Coroutines允许您在生成例程实际完成之前向调用例程屈服。我知道有一个Java库可以重写字节码以支持协同；如果您是针对Java的话，您将不得不研究它。

您提到的两个变体本质上是可供选择的:多线程或排队您想要产生的中间结果。在您的特定情况下，算法中没有交互，因此您可以预先创建整个队列，而不是在算法中进行检查。

编辑：，我不确定递归是否有那么好的效果；我的知识更多的是理论上的。不过，我认为您应该能够直接或通过在递归调用中额外地生成多个级别。