Pattern to coordinate between a recursive algorithm and an event-driven consumer

Question

Consider this classic recursive pseudocode solution to the Tower of Hanoi problem:

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

... and consider the event loop in a display engine such as Processing

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

      updateCoordinates();
      drawMovingDisc();
  }

What patterns are there to coordinate between the two?

Two options come to mind:

Threads and a queue

Start the recursive function in its own thread. moveSingle() writes a move to a FIFO queue. This may block if the queue is at capacity. getNextMove() reads a move from the queue.

I'm sure this works fine, but I'm curious if there's a pattern that avoids threading.

Use an explicit stack instead of recursing

Rewrite the recursive algorithm to use a LIFO queue in the heap, rather than the call stack. Something like:

 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
 }

... and again, this works, but we lose the expressive power of recursion using the call stack to preserve state.

Is there another technique I've failed to spot?

Note, although I've chosen the example of Tower of Hanoi and Processing, this is intended as a general problem of integrating a recursive algorithm with another interface that wants to poll for updates. So I'm not interested in answers like "You don't need a stack to solve Hanoi" -- I know that.

Answer 1

What you're looking for are coroutines, although they are missing in some languages (e.g. Java). Coroutines let you yield to the calling routine before the yielding routine has actually finished. I know that there is a library for Java that rewrites bytecodes to support coroutines sort-of; you'll have to look into it if you're targeting Java.

the two variant you've mentioned are essentially the alternatives: Multithreading or queuing the intermediate results you want to yield. In your particular case, there is no interaction in your algorithm, so you might actually create the whole queue in advance instead of checking inside your algorithm.

EDIT: I'm not sure if yielding works that well with recursion; my knowledge is more theoretical. I think you should be able to yield multiple levels either directly or by additionally yielding in your recursive calls, though