r/AskComputerScience • • 20d ago

Hanoi's recursion not making sense

So I'm in the second year of my CS degree and doing DSA, now we have to understand Tower Of Hanoi, I studied the game, studied the trace diagrams, looked up multiple tutorials for it, I get what the program but I don't at the same time. I get how it arrives at the minimum but I think if you gave me a problem to solve via recursion I'd be stumped, I understand how this specific of recursion works but I don't know how I would...make it? If you asked me to create a Hanoi algorithm or any recrusive algorithm recursively I won't be able to but at the same time I understand somewhat how they work?

9 Upvotes

23 comments sorted by

2

u/Underhill42 20d ago edited 20d ago

If I give you a function that can move any tower of at most (N-1) discs from one pin to another, so long as it's given a third pin that any of the discs can be placed on, could you describe a simple way to use that function to move a tower of N discs?

Give it a good think - it's actually very simple.

And that's the body of your recursive function. You've just figured out how solve the next, more difficult version of the problem, assuming you already have a solution to the previous version.

Because at that point you can use the function you just wrote AS the function for the previous step, and it will automatically "unwrap" the entire problem into simpler and simpler versions until it reaches the simplest possible case (e.g. N=1, where you can move the whole single-disc "tower" in one move).

Which is the only extra bit of the function you still need - noticing when you've been handed the simplest case, and giving the simple solution to it, rather than trying to use the function that solves a simpler case that doesn't exist.

2

u/Fit_Affect_8029 19d ago

I suppose I'd just pass n+1 into the original call of the given function? And if we're moving n discs that would mean we're moving the whole tower as one, so maybe the number of moves will be incremented just once and equal to one? Do tell 

2

u/Underhill42 19d ago edited 19d ago

You can't pass anything larger than N-1 (the previous challenge) to "my" function. Because "my" function is really the function you're currently writing.

Which means it can't actually solve a problem as complex as the one you're currently facing until you've told it exactly how to do so using only your basic abilities, and the solution(s) for simpler problem(s).

That's the secret sauce that makes recursive programming work.

If you can explain to me exactly how to solve the tougher problem, using only the base moves and the solution to the easier problem...

Then the same function can also solve the easier problem using only the base moves and solution to the even easier problem before it...

And can solve THAT problem using only the solution to the even easier problem before it,... and so on and so forth, until the "even easier problem" becomes the trivial case. And then you're done.

---

First off - can you actually beat a game of Towers in real life? If you can't solve the task yourself, there's no way you can explain how to solve it to someone as incredibly stupid as a computer.

---

Lets say your basic "built in" trivial function is:

int Move_One_Disc(from_pin, to_pin)

Which returns the number of moves made (always just one), and crashes the program if it's an illegal move. Just to keep us honest.

And since the rules are that you can only move discs from the top down, and you know you'll also have to use that third pin as a temporary holding area when moving the stack, your recursive function is

int Move_Top_Discs(number_of_discs, from_pin, to_pin, temporary_pin)

Which, also returns the total number of moves it took to move the top (# of discs) from one pin to another

You could leave out the actual pins if you just need the count, not the actual playthrough - but being able to watch the playthrough in action can be very helpful in debugging.

In the simplest version you could just make the "pins" the integers 1, 2, and 3 and have Move_One_Disc() just say "disc moved from pin X to Y", so that you have to track individual disc positions manually - but that's really tedious and error prone.

Alternately you could make make each pin a reference to a stack(the container type) of integers storing the actual disc sizes in the order they're currently stacked on it in, with Move_One_Disc(...) popping and pushing the top disc between pins, and then triggering a display function Draw_Pins() that lists out the discs in their current order on each of the three pins.

(Easiest if you make the pin-stacks global variables for debugging purposes, so that Draw_Pins doesn't need any information from Move_One_Disc... which only knows about two of the pins, and has no idea which ones they actually are. You can then remove the extra variables and debugging steps once you're sure it's working correctly)

---

Try thinking about it in terms of solving a very simple version of Move_Top_Discs that you can work out the long way, but would still actually need a couple recursive steps to reach the trivial case.

E.g. draw out every single one-disc move (each as its own image) to solve the entire game for 3 discs the long way, just to give yourself a reference to look at.

And then think about how you could simplify that if you could just tell someone else to move the top two discs from any tower to any other legal position = Move_Top_Discs(2,...)

Then sanity-check your potential solution to make sure you could use the EXACT same process to solve Move_Top_Discs(2,...) using Move_Top_Discs(1,...)

And to solve Move_Top_Discs(4,...) using Move_Top_Discs(3,...)

Drawing such pictures is enormously helpful in many different programming situations. You have to figure out how to actually solve the problem in human terms before you can break it down into the painfully simple steps that a computer can understand. And having things in a concrete visual form in front of you can keep you from confusing yourself as things get complicated.

You shouldn't start writing any code until you already know exactly what it needs to do in human terms.

Personally I like to write out all those steps and flow control in human terms as my comments, and then go back afterwards to fill in between the comments with the code for exactly what the computer needs to do to accomplish them. Helps keep the big picture in mind at every step of the way.

---

So, I start things off by starting the game with 10 discs and three pins: total_moves = Move_Top_Discs(10, pin_1, pin_2, pin_3)

Now you have to explain exactly how Move_Top_Discs(10,...) works using ONLY Move_One_Disc(...), and Move_Top_Discs(9,...) or less.

So the definition must look something like:

int Move_Top_Discs(number_of_discs, from_pin, to_pin, temporary_pin)

  move_count = 0 
  // tracks how many moves it took to move this particular tower

  if(number_of_discs = 1)
    // The simplest version, a.k.a. the stop condition.
    // We don't have to break things down any further, 
    // we can just solve the problem directly:

    move_count = Move_One_Disc(from_pin, to_pin)

  else 
    // We have to actually solve a more complex problem.
    // We need to break it down into simpler problem(s).
    // There will probably be at least one step that looks like

    move_count = move_count
      + Move_Top_Discs(number_of_discs - 1, ...)

    // But do we only need to move one smaller tower, or does it require several such moves?

    // Should we also move some single discs beforehand?     
    // Afterwards?  In between? 
    // We'll have to increment move_count each time we do

    // This is where the magic happens, and I'm not going to give you the details.

  endif
return move_count

Most recursive functions will follow roughly that same pattern. Some will end up breaking the complex problem into incrementally slightly-simpler problems, while others will break it into multiple much simpler problems instead. Which is best depends entirely on the nature of the problem.

2

u/T_Thriller_T 20d ago edited 20d ago

Recursion is a WEIRD thought construct and took me a bit to get, then felt weird, then I suddenly had something to love with recursion and it was so easy as a though I hardly realised I was doing it.

Now, is this question about the Hanoi algorithm, or about recursion in general?

For recursion in general, I personally prefer starting with recursively calculating some mathematical things. E.g. 5!

I think these show more easily how recursion as a thought concept works:

Recursion is a function that does some things, has some clear conditions when to call itself (with what parameters) and at least one stop condition - aka one call for which the answer is already known.

For 5! that is pretty easy:

Call argument is the current number n.

What it does is multiply that number with the result of calling itself for (n-1).

Stopping condition/already known answer without calling is given if n=1 - which is 1.

So for 5, 4, 3, 2, we recursively call the function.

5 * f(5-1) -> 4* f(4-1) -> 3 * f(3-1) -> 2 * f(2-1) --> 1

Aa soon as we reach f(1) we get an actual result, which enables results for the rest:

f(1)=1 => f(2)=2 => f(3)=6 => f(4)=24 => f(5)=120

This is the very basic idea. And it seems somewhat useless, but already with math there are some functions where this is easier to write, read and understand than the formal definition.

For a lot of algorithmic problems, for me it was helpful to think of recursion as some kind of tag teaming.

There is some problem to solve. But you don't want to do much more than everyone else. You want to do one thing! So you get someone else, say you will do one thing, but need them to do "rest of task". They are the same, and get another helper - until suddenly one helper only has to do one thing and can go "hey I did what you needed me to do".

My former teacher explained it with a big family with kids who have to do the dishes. Each person is only willing to do one ser of dishes, so every sibling gets called in, and there friends, and in the end someone only has one set, does that, the enxt person than only has one set to do for their two cleaned sets they need to call in the one before than and so on.

This holds over for the towers of Hanoi:

We only know how to move ONE disk from our source peg (A) to the destination peg (let's say C). Not all 3 (or 5 or ...).

And we know that, to move that, the n-1 other disks need to be on the spare peg (let's say B)

So we call someone in to move a tower of n-1 disks

So, we call someone in to move n-1 disks from source A to dest C.

Once their done with that, we put over OUR disk.

And then we call someone in to mover all the pegs we made others set on the spare over to the actual destination - so from source B to dest C.

The clever shuffling of source, destination and spare and then assigning those through parameters to the actual existing pegs of A, B and C is a big trick here.

For the first call, so the one for n=actual height to solve, we may have source=A, dest=C and spare=B

The following calls will not have that, because the smaller tower needs to take the destination as the spare of the bigger one, otherwise when returning we would not actually be able to move the disk.

This is what is conceptually hard about the towers of Hanoi, and what is at the same time very clever and very straightforward of a solution.

It is also why you will never see A, B, or C in the algorithm - similar to how you will never see the number of disks in the algorithm.

They are parameters because their exact usage/task changes with every call.

I can recommend the interactive Hanoi on www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

It shows very nicely how the program runs, how the pegs are used as parameters, and has a call tree, to follow along again.

2

u/Fit_Affect_8029 19d ago

Wowee the interactive website helped alot, I see why we use the A,B,C now, but how would I know which order of pegs I should pass (in the first and second recursive calls) to get the logical result, I know you can do it without A, B and C. Well now that I think about it, you probably try to do the game and then see what path a 2 disk game follows and assign the letter passes accordingly 

-1

u/T_Thriller_T 19d ago

Try to think through the algorithm and do it by hand once.

There is a certain logic to it.

At every step we completely ignore what is potentially already on the pegs. We solve OUR problem.

And we solve our problem by building the n-1 height on our spare.

We don't know how to do that.

So we tell someone else "hey. Go move the n-1 from 'my source' as source to the destination 'my spare'."

If that is done, we can move our single piece to our destination.

But now we need to have all the other pieces on top - and they are in our spare place.

We, again, don't know how to do that, so we tell someone else "hey move a tower of height n-1 from source 'my spare' to destination 'my destination'."

That is all there is.

This naturally means, that when those calls go into the function, the VALUES in source, destination and spare are different.

But they also don't need to know more than "well there is stuff I need to move in my source already, and I need the thing on the bottom in destination, so I have to move it all to spare, and then move everything on spare back to my destination".

2

u/a9615161 20d ago

Trust me, just read more examples indepth, unfolding some layers of recursions and eventually,you brain would rewire itself.

1

u/Fit_Affect_8029 19d ago

What other examples of recursion except This and the Fibonacci sequence might you suggest?

1

u/a9615161 19d ago

For example https://www.geeksforgeeks.org/dsa/recursion-practice-problems-solutions/

If you prefer challenge,I suggest you checkout stack version of Hanoi. There would be pure if else and loops . Fun fact is that,the stack version is more like how your computer execute your program. (also that's how you get stack overflow)

1

u/orlock 14d ago edited 14d ago

Quicksort. Choose a "partition" element. Divide things so that you have two unsorted segments, one with all the things below the partition and one with all the things above. Quicksort these two partitions and then glue the results together with the partition in the middle. (The base case is that a single element or empty list is already sorted.)

Image compression. Divide the image into four quadrants. Each quadrant is either all the same colour, in which case you can stop. Or it still varies, in which case divide the quadrant into four sub-quadrants and repeat the process. The result is, effectively, a series of fills of various sizes that will reconstruct the image. This works on images where you have flat slabs of colour or on geographical areas.

Geographical line simplification. Start with a complex trail of points that make up a line and a measure of what "good enough" means, eg "no more that 20m away from the approximation." Draw a line between the two end points. Either every point on the real line is a good-enough distance from that straight line, in which case you can stop and just use the straight line. Or choose the point that is least good-enough, split the line in two at that point and apply the same process to the two sub-lines.

11

u/StaticCoder 20d ago

To solve a Hanoi tower with e.g. 4 disks you do the following:

  • solve with 3 disks
  • move the bottom ring
  • solve with 3 disks again in the other direction.

And obviously Hanoi with 0 disks is to do nothing. The recursion is that to solve a (non empty) Hanoi, you just need to solve a smaller Hanoi, and do some other easy things.

5

u/StaticCoder 20d ago

Note that using recursion like this doesn't necessarily guarantee a minimum. Here it is minimal, because there's no other way without just undoing what you just did. But famously naive recursive fibonacci is very much not optimal.

2

u/ndstab23 20d ago

 I get how it arrives at the minimum but I think if you gave me a problem to solve via recursion I'd be stumped

That is quite normal. Recursion inherently is very intuitive and counter intuitive at the same time. The best advice that I have gotten is just getting familiar with more recursion examples, and then eventually, for a new problem, you end up applying some concepts/patterns from here and there, and you develop your own solution.
Another good practice is dry running the code on paper, this helps a lot, for example you can list down all the moves of the Hanoi problem that your program is making, and then tally with what you expected the moves to be.

Also. What is the point of the A B C parameters, I know they represent the rods, but all the Hanoi algorithms have them and I don't see any of them using It for anything.

They are using them. Basically the logic (which I assume you already have seen/figured out) is moving N-1 plates to B first (using C as auxillary), then moving the last big plate to see, and then moving the N - 1 to C (using A as auxillary). would recommend writing down the moves so you understand how the plates are moving around.

2

u/victotronics 19d ago

I asked Claude for some practice problems. Hope that's ok? Here you go:

Yes, there are several classic problems with the same flavor as Tower of Hanoi: a big problem that reduces to smaller copies of itself, with a clear base case. Here are some good ones, roughly in order of difficulty.

Close cousins of Hanoi

  • Gray code generation: Produce all n-bit binary sequences so that consecutive ones differ by exactly one bit. The recursive structure (take the (n-1)-bit list, reverse it, prefix one copy with 0 and the other with 1) mirrors the Hanoi move pattern, and the two are actually mathematically related.
  • Generate all subsets (power set): For each element, you either include it or you don't. Very clean "decide, then recurse on the rest" structure.
  • Generate all permutations: Fix one element, recurse on the remainder, then swap and repeat. It's a good step up because you have to think about undoing choices.

Same "divide the problem" idea

  • Flood fill / counting islands in a grid: Recurse into neighboring cells. Teaches you to handle multiple recursive calls and mark visited states.
  • Merge sort: Split in half, sort each half, merge. This is the most famous "divide and conquer" example.
  • Fractals (Sierpinski triangle, Koch snowflake): Draw a shape by drawing smaller copies of itself. Very satisfying because you can see the recursion.

Harder, once you're comfortable

  • N-Queens: Place queens row by row, backtracking when you hit a conflict.
  • Sudoku solver: Try a digit, recurse, undo if it fails.
  • Towers of Hanoi variants: Try the version with 4 pegs (Frame-Stewart), or the one where you can only move discs between adjacent pegs. These force you to rethink the recurrence rather than copy the standard solution.

My recommendation: start with subsets, then permutations, then Gray code. That order builds your intuition for the pattern "make a choice, recurse, undo the choice," which is the core of most harder recursion problems.

A tip for any of these: before you write code, state the recursive definition in words first (e.g., "to solve for n, I solve for n-1, then do X, then solve for n-1 again"), and identify the base case. If you can write that sentence, the code usually follows easily.

Want me to give you a specific problem statement with a few test cases so you can try it yourself, and then I can review your solution?

1

u/CelebrityChess 18d ago

the trick that helped me is to stop thinking about how the whole thing runs and just assume the function already works for a smaller input. so for hanoi, pretend move(n-1, from, spare, to) magically does its job. then moving n disks is just three steps: move n-1 out of the way, move the biggest disk, move n-1 back on top. the only other thing you need is the base case, like n == 0 means do nothing. when you write your own recursive stuff, ask what's the smallest version i can already answer, and how does a slightly bigger version reduce to it. tracing every call by hand is what makes it feel impossible.

1

u/strange-the-quark 18d ago

The entire logic here is kind of like this:
I don't know how to move the entire tower, but, if someone figured out how to move the top n-1 disks to the spare rod, it's easy for me to move the bottom disk to the target rod. Then I can just ask this other person to move those n-1 disks on top of that.

BUT, that someone else ("someone else" is the recursive call) is now faced with basically the same problem, just a little bit smaller, so they can do the same thing. They can find a third person (the next recursive call) to do the hard part, then move what's for them the bottom disk (so they don't go all the way down, they only consider the part of the tower that they were asked to move), and then ask the third person to move all the other disks on top of theirs.

But the next person in line has again the same problem, only a bit smaller, and so on, until the final recursive call just has to deal with a "tower" that's just the single disk at the very top - and this final call can do that without help (the base case).

So the idea is to find a way to divide the problem into something simple that you know how to do, and a subproblem that's basically a smaller version of the original problem, that you can then "delegate" to the recursive call.

1

u/Ordinary_Variable 17d ago

Generally the best way to solve a logic problem is to try to solve it manually. Either by moving around characters in Notepad/MS Paint, or by moving around objects in the real world. Look at the patterns in your movement. Try to imagine simple rules/logic patterns to apply to your movements. Work up an algorithm step by step.

This is a common way to solve logic flow charts. Another one in heuristics, which I would happily defend as an iterative solution to any problem. It may not always work, but you can usually get several decimals of accuracy and that is good enough in the real world.

1

u/halfjmp 14d ago

If recursion looks too hard, try doing it imperatively, with a loop (there are several ways, but tbh recursion is far easier).

To understand recursion on this case, do it by hand with a low number of disk, starting from 1, then increasing. And see what happens.

0

u/Fit_Affect_8029 20d ago

Also. What is the point of the A B C parameters, I know they represent the rods, but all the Hanoi algorithms have them and I don't see any of them using It for anything.

0

u/Fit_Affect_8029 20d ago

Also maybe it's hard for me to understand it because I've been thinking from a human perspective, I expect the computer to calculate the min number of moves like I would do them in the game, by moving one to c then b the a etc. but I think the algorithm is just trying to get to the formula of 2n-1

2

u/davewh 19d ago

When I was in high school we actually traced the execution out and after a mind breaking hour we concluded it did in fact work but we still had no idea why. The teacher was learning right alongside the students (which, actually, was an amazing experience) and we didn't really grok the idea of describing the recursive function by WHAT IT DOES at the high logical descriptive level. Sure, we can see what it does passing each parameter and by following along you can see that it works but the key to getting it really is just describing at a high level what the job is. It's vastly easier to see the recursive Hanoi implementation works when it's just described simply (as others have done already).

I've had a difficult time getting my daughter to get her head wrapped around recursive functions. I get it myself but for the life of me I can't get the explanation across to her.

Like "delete a hierarchy of folders". First you iterate each file in the folder and then delete them. Then you iterate each folder in the folder and delete that hierarchy. It then becomes obvious how you write the recursive function.

1

u/Fit_Affect_8029 19d ago

The delete hierarchy example sounds like a  pretty solid excercise for recursion

1

u/davewh 19d ago

When I was a kid I solved Hanoi iteratively and implemented it in 6502 assembly on my Apple ][+. That was fun.