Tower of Hanoi: Recursive Algorithm

by

Actually, the section from where you took that code offers an explanation as well:

To move n discs from peg A to peg C:

  1. move n−1 discs from A to B. This leaves disc #n alone on peg A
  2. move disc #n from A to C
  3. move n−1 discs from B to C so they sit on disc #n

It’s pretty clear that you first have to remove n − 1 discs to get access to the nth one. And that you have to move them first to another peg than where you want the full tower to appear.

The code in your post has three arguments, besides the number of discs: A source peg, a destination peg and a temporary peg on which discs can be stored in between (where every disc with size n − 1 fits).

The recursion happens actually twice, there, once before the writeln, once after. The one before the writeln will move n − 1 discs onto the temporary peg, using the destination peg as temporary storage (the arguments in the recursive call are in different order). After that, the remaining disc will be moved to the destination peg and afterwards the second recursion compeltes the moving of the entire tower, by moving the n − 1 tower from the temp peg to the destination peg, above disc n.

More Related Contents:

  1. Way to go from recursion to iteration
  2. Solution for “Fatal error: Maximum function nesting level of ‘100’ reached, aborting!” in PHP
  3. Determining complexity for recursive functions (Big O notation)
  4. Prolog Accumulators. Are they really a “different” concept?
  5. What is recursion and when should I use it?
  6. How can I make recursive templates in AngularJS when using nested objects?
  7. Is Cmake set variable recursive?
  8. Recursive function causing a stack overflow
  9. “application: not a procedure” in binary arithmetic procedures
  10. count the number of calls of a clause
  11. recursive variadic template to print out the contents of a parameter pack
  12. Recursion vs loops
  13. Real-world examples of recursion [closed]
  14. I got “scheme application not a procedure” in the last recursive calling of a function
  15. Implications of foldr vs. foldl (or foldl’)
  16. How does the fibonacci recursive function “work”?
  17. Examples of Recursive functions [closed]
  18. Is it possible to make a recursive closure in Rust?
  19. What does “Overflow evaluating the requirement” mean and how can I fix it?
  20. SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process
  21. How does recursive algorithm work for Towers of Hanoi?
  22. Which recursive functions cannot be rewritten using loops? [duplicate]
  23. Power by squaring for negative exponents
  24. How to recursively find and list the latest modified files in a directory with subdirectories and times
  25. Javascript recursive array flattening
  26. Confusing […] List in Python: What is it?
  27. Why are functions in OCaml/F# not recursive by default?
  28. PHP Recursively unset array keys if match
  29. Breaking out of a recursion in java
  30. PHP convert nested array to single array while concatenating keys?

Leave a Comment