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.