8

I have seen the other Questions on SO about the Recursive function and I have read the responses but I still can't get the algorithm to click in my head

var hanoi = function (disc, src, aux, dst) {

  if (disc > 0) {
    hanoi(disc - 1, src, dst, aux);
   document.write('Move disc ' + disc + ' from ' + src + ' to ' + dst);
    hanoi(disc - 1, aux, src, dst);
  }
}

hanoi(3, 'Src', 'Aux', 'Dst');

How does the document.write(...), ever run. My Logic is First time we run the function disc is > 3. then we recursively call the function again skipping everything below so how does the document.write get a chance to run?

I understand recursion (done the basic examples) but i still can't see how you get an output. If there is a way i can run it visually and see it in action, that would help alot.

Mike Diaz
  • 2,045
  • 4
  • 32
  • 55

1 Answers1

22

You can think of what will happen as a call tree (time moves from top to bottom):

hanoi(3, ...) =>
 |-> hanoi(2, ...) =>
 |    |-> hanoi(1, ...) =>
 |    |    |-> hanoi(0, ...) =>
 |    |    |    \-> (does nothing)
 |    |    |-> document.write(...)
 |    |    |-> hanoi(0, ...) =>
 |    |    |    \-> (does nothing)
 |    |  <-/ [hanoi(1, ...) finished]
 |    |-> document.write(...)
 |    |-> hanoi(1, ...) =>
 |    |    |-> hanoi(0, ...) =>
 |    |    |    \-> (does nothing)
 |    |    |-> document.write(...)
 |    |    |-> hanoi(0, ...) =>
 |    |    |    \-> (does nothing)
 |    |  <-/ [hanoi(1, ...) finished]
 |  <-/ [hanoi(2, ...) finished]
 |-> document.write(...) [halfway done!]
 |-> hanoi(2, ...) =>
 |    \-> [same pattern as the first time, with different data]
 \-> [hanoi(3, ...) finished]
Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • +1 I was about to write the same thing, but yours is more readable. The key, I think, is to think about each `hanoi()` not as a `GOTO` but rather as a subroutine of the previous `hanoi()`. In that sense, it does have `disc` go to 0, but it still has three `hanoi`s open, and they would continue to run. "Annie's going to leave after Bob leaves, who leaves after Cindy leaves, who leaves after Doug leaves" or some such. – brymck Aug 15 '11 at 02:00