How does recursive algorithm work for Towers of Hanoi?

by

Probably the simplest solution to the Towers of Hanoi works like this:

To move x discs from peg A to peg C, using peg B as an “aux” peg:

  1. Move x-1 discs from peg A to peg B, using peg C as the aux peg.
  2. Move the x‘th disc from peg A to peg C (no aux peg needed, cause you’re only moving one disc).
  3. Move the x-1 discs from peg B to peg C, using peg A as the aux peg.

Note that in order to move x discs, you have to move x-1 discs. You can just use the same function to move those x-1 discs, and just switch which pegs are the source, dest, and aux pegs. That’s what makes Towers of Hanoi such a common example of recursion, and that’s the kind of pattern you need to see in a problem in order to make recursion work for you. It need not be “move x-1 discs”, of course…it could be something like “list this subfolder”. Trees (like a directory with subfolders and such) are another place where recursion shines. As do other jobs where in order to do the job on an item, you may need to do the same job on sub-items.

Now, in order to have useful recursion, you need a “base case” — a condition where the recursion will stop. If you don’t, the code will run forever (or at least til it runs out of memory or overflows the call stack). The base case here occurs when x == 0 (since moving 0 discs means you do nothing, due to the if around the meat of the function). It could also be when x == 1, as then you don’t have to recurse, but the extra if before each hanoi call would add a bit of noise (and the main benefit to a recursive solution is its simplicity). Anyway, when x == 0, the function returns without doing anything. The function that called it (which had x == 1) now gets to continue doing its thing — in this case, saying “move disc 1 from src to dest”, and then calling the hanoi function again with the args switched.

The flow goes a bit like this:

hanoi(3, src, aux, dest)
  hanoi(2, src, dest, aux)
    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "Move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op

    print "Move 2 from src to aux"

    hanoi(1, dest, src, aux)
      hanoi(0, dest, aux, src)        // no op
      print "move 1 from dest to aux"
      hanoi(0, src, dest, aux)        // no op

  print "move 3 from src to dest"

  hanoi(2, aux, src, dest)
    hanoi(1, aux, dest, src)
      hanoi(0, aux, src, dest)        // no op
      print "Move 1 from aux to src"
      hanoi(0, dest, aux, src)        // no op

    print "Move 2 from aux to dest"

    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op

More Related Contents:

  1. Javascript a recursive function with no clear base case?
  2. How can I convert this JavaScript recursive function to an iterative one? [closed]
  3. How do I replace while loops with a functional programming alternative without tail call optimization?
  4. Building a promise chain recursively in javascript – memory considerations
  5. How does this recursion work?
  6. Recursion in Angular directives
  7. Typescript recursive function composition
  8. Recursively print all permutations of a string (Javascript)
  9. javascript: recursive anonymous function?
  10. Check for repeated characters in a string Javascript
  11. What are the js recursion limits for Firefox, Chrome, Safari, IE, etc?
  12. JavaScript recursive search in JSON object
  13. Javascript recursive array flattening
  14. A clearer explanation for recursion and flow of execution in JavaScript?
  15. Run multiple recursive Promises and break when requested
  16. Recursively filter array of objects
  17. Javascript recursive function not returning value?
  18. ES6 Tail Recursion Optimisation Stack Overflow
  19. Generate permutations of JavaScript array [duplicate]
  20. Can I use additional parameters in recursion problems?
  21. Why does this recursive function return undefined?
  22. recursive function vs setInterval vs setTimeout javascript
  23. Javascript recursion from Eloquent Javascript
  24. Jquery Ajax beforeSend and success,error & complete
  25. Recursive Promises Not Returning
  26. Await an iterative function without delimiter in JS
  27. How to get all keys with values from nested objects
  28. javascript return of recursive function [duplicate]
  29. JavaScript Performance Long Running Tasks
  30. Renaming object keys recursively

Leave a Comment