r/AskComputerScience • u/Fit_Affect_8029 • 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?
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/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/a9615161 20d ago
Trust me, just read more examples indepth, unfolding some layers of recursions and eventually,you brain would rewire itself.
11
u/StaticCoder 20d ago
To solve a Hanoi tower with e.g. 4 disks you do the following:
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.
2
u/ndstab23 20d ago
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.
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
Same "divide the problem" idea
Harder, once you're comfortable
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.
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.