algorithm - 在递归算法和事件驱动的消费者之间进行协调的模式

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);
      }
  }

... 并考虑显示引擎中的事件循环，例如 Processing

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

      updateCoordinates();
      drawMovingDisc();
  }

两者之间有什么模式可以协调？

我想到了两个选项:

线程和队列

在自己的线程中启动递归函数。 moveSingle() 将移动写入 FIFO 队列。如果队列已满，这可能会阻塞。 getNextMove() 从队列中读取一个 Action 。

我确信这工作正常，但我很好奇是否有避免线程的模式。

使用显式堆栈而不是递归

重写递归算法以在堆中使用 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
 }

...再一次，这可行，但我们失去了使用调用堆栈来保存状态的递归表达能力。

是否还有其他我没有发现的技术？

请注意，虽然我选择了汉诺塔和 Processing 的示例，但这是将递归算法与另一个想要轮询更新的接口(interface)集成的一般问题。所以我对诸如“你不需要堆栈来解决 Hanoi”之类的回答不感兴趣——我知道这一点。

Answer 1

您正在寻找的是协同程序，尽管它们在某些语言(例如 Java)中缺失。协程让您在让出例程实际完成之前让出调用例程。我知道有一个 Java 库可以重写字节码以支持协程；如果您的目标是 Java，则必须研究它。

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

编辑: 我不确定 yield 是否适用于递归；我的知识比较理论化。不过，我认为您应该能够直接或通过在递归调用中额外产生多个级别来产生多个级别