The above pattern is both what makes recursion powerful and hard to understand. Thus, the same function is called again with n-1 discs, and the pattern continues until we reach the base case where the number of discs is equal to one and the base case solution executes. This makes sense since moving n-1 discs all together is not a legal move.
However, you will notice that we are calling the original function again whenever we call the function with a number of discs greater than zero. With this logic, we can define a function that looks like the algorithm in the figure below. Once we have the largest disc on the destination peg, we need to move the original n-1 discs (now on the spare peg) to the destination peg.
#Scheme hanoi towers free#
Then, we are free to move the largest disc (nth disc) to the destination peg. First, we need to move n-1 discs to the spare disc. Source: Brandeis University, CS DepartmentĬonceptually, we can break the problem down into a few moves. As shown in the diagram below, let’s assume that the ‘A’ peg is the source peg, ‘B’ peg is the spare peg, and the ‘C’ peg is the destination peg. The goal is to move all of the discs from the source peg to the destination peg one at a time without ever having a larger disc on top of a smaller disc. This post is intended to help shed light on the latter.įor those not familiar with the rules, there are three pegs (source, spare, and destination).
Second, once you have an algorithm to solve the problem, it’s not exactly clear how the computer executes the recursion calls. First, recognizing the pattern was far from obvious (I spent hours painstakingly moving paper discs around). From my experience, what makes Towers of Hanoi difficult is two-fold. Needless to say, it was really challenging.
#Scheme hanoi towers how to#
ĭuring my second week of learning how to code at the Flatiron School, we were given the Towers of Hanoi problem to apply our new found knowledge of recursion. Christopher is currently in the Ruby-003 class at The Flatiron School. The following is a guest post by Christopher Lee and originally appeared on his blog.
0 kommentar(er)
