Trying to understand recursion better

Question

3.67/5 (2 votes)

See more:

Hi.
I am studying recursion at the moment and trying to understand it well.
Got an example im working on and need to figure out step by step what is happening.
So far i understand certain parts of it, but can't seem to figure out how it all goes together.

Can anyone please explain how the recursion is being called and how parts are being moved?
This is the code:

C#

private void btnExecute_Click(object sender, EventArgs e)
       {
           Hanoi(1, 2, 3, 3);
       }
       void Hanoi(int Tower1, int Tower2, int Tower3, int n)
       {
           if (n == 1)
               txtOutput.Text += "Move from " + Tower1 + " to " + Tower3 + "\r\n";
           if (n > 1)
           {
               Hanoi(Tower1, Tower3, Tower2, n - 1);
               Hanoi(Tower1, Tower2, Tower3, 1);
               Hanoi(Tower2, Tower1, Tower3, n - 1);
           }
       }

It is outputting the following and i need to figure out how its working:

Move from 1 to 3
Move from 1 to 2
Move from 3 to 2
Move from 1 to 3
Move from 2 to 1
Move from 2 to 3
Move from 1 to 3

Posted 4-Feb-14 19:33pm

Member 10540766

Updated 27-Feb-17 4:12am

Add a Solution

Comments

Sampath Lokuge 5-Feb-14 1:45am

The best thing which you can do is,just put a brake point and understand the way it recessives.

Sergey Alexandrovich Kryukov 5-Feb-14 1:48am

Do you understand how call stack works? If you understand that, it gives you the key to a number of deep understanding of key things: recursion, structural exception handling and threading...
—SA

phil2846 27-Feb-17 10:13am

I've been looking at this problem too for school. This is my output from the txt window logging the values of the variables along the way. a is a reference to which method has been called. What I mainly don't understand at this point is how n increments in one of the steps. I'm not entirely following the logic of the recursion calls either.

call n=3 t1=1 t2=2 t3=3 a=1
call n=2 t1=1 t2=3 t3=2 a=1
call n=1 t1=1 t2=2 t3=3 a=1
Move from 1 to 3
call n=1 t1=1 t2=3 t3=2 a=2
Move from 1 to 2
call n=1 t1=3 t2=1 t3=2 a=3
Move from 3 to 2
call n=1 t1=1 t2=2 t3=3 a=2
Move from 1 to 3
call n=2 t1=2 t2=1 t3=3 a=3
call n=1 t1=2 t2=3 t3=1 a=1
Move from 2 to 1
call n=1 t1=2 t2=1 t3=3 a=2
Move from 2 to 3
call n=1 t1=1 t2=2 t3=3 a=3
Move from 1 to 3

3 solutions

Solution 3

Yes. Recursion can simplify a solution quite a lot.
But reading it may be problematic.

You are trying to understand 2 problems at the same time.

1. How the recursion works.

The easiest form of recursion is calling the same function from just one place in the code.
Like calculating the factorial.

int CalcFactorial(int n)
{
if (n <= 1)
return 1;
else
return n * CalcFactorial(n - 1)
}

This one is quite easy to follow, because the complexity is low.
There is only 1 branch to follow. It can easily be converted to a for loop.

Your example above is quite complex to follow,
because the depth of the recursion is hard to grasp.
And the result from all of them influences the result.

2. How to solve the towers of Hanoi

There is only 1 way to move a ring.
put a smaller on top of a bigger or on an empty place.

In order to move 3 rings which are on top of each other.
You put the smallest on one stick.
Put the middle on the other free stick.
Move the smaller to the middle one.
Move the biggest one.
Move the smallest away from the middle one.
move the middle one to the biggest, and finally move the smallest on top of the middle one.
Done.

The three calls to the function corresponds to the number of towers available,
and indirectly how you move the rings between them.

I can confess that I have hard time to follow the recursion too. :D
For each call to Hanoi(), you get 3 new sub branches.
I would take a pen and pencil and write out the recursion tree.
That is the best way to understand it.
I would definitely do it in this case, since the number of calls are so few.

Posted 4-Feb-14 20:15pm

Mattias Högström

Updated 4-Feb-14 20:16pm

v2

Comments

Member 10540766 5-Feb-14 22:21pm

Ok so for each number in the Hanoi(1,2,3,3); we run the 3 sub branches?

Eg; for Hanoi(1) its:
Hanoi(Tower1, Tower3, Tower2, n - 1);
Hanoi(Tower1, Tower2, Tower3, 1);
Hanoi(Tower2, Tower1, Tower3, n - 1);

The first line would be n(3)-1 which is 2, but i dont get what im doing with the sub branches.
First line = ?
Second line = ?
Third line = ?

Then for Hanoi(2) and (3) i still dont get it, but by understanding what happens in the first call i will understand the rest.
Can you please explain that one?

Mattias Högström 6-Feb-14 4:04am

The 3 lines looks almost the same.
What changes is the towers you move between.

You have to run it step by step in you head or use pen and pencil.
Do you know how to traverse a binary tree in order to visit all nodes?
Instead of a binary tree, it is a tree which splits in three.

The program completely finishes all left branches first.
From the beginning all rings are on the first tower.
We enter Hanoi(1,2,3,3)
Then we enter the recursed Hanoi(1,3,2, 3-1)
Then we enter the recursed version of Hanoi(1,2,3 2-1) again.
Then he print "Move from Tower #1 to Tower #3", because n == 1
#1 and #3 are tower 1 and tower 3, the first time.
This happens at depth 2.
Then it returns to depth 1, and there it has to continue with the middle and right branch.

What he is doing, is doing a composed move, which requires three sub moves.
On the second call he takes into account that the rings have moved in the first call.
(He moves around the position of the tower). Then he continues to move the rings.

Recursion is usually not this hard.
This kind of solution is not something you just invent by accident.
You usually make the solution or part of it (the tree with the moves) on a paper.
Then generalise and abstract an algorithm.

What the author probably realised was that he could abstract it into three identical sub trees.
Then he found a clever way to traverse the tree from left to right using recursion.

Understanding the code without imagining the call tree is close to impossible.

Member 10540766 10-Feb-14 21:57pm

Im having trouble following the code even with a breakpoint, any advice on an easier way to follow it? Or to write it out step by step??

Solution 1

SQL

Hi,

If you would have known calling a method in Object oriented programming understanding Recursion is not a big problem

1. Calling a method itself by changing the parameters(Hanoi(Tower1, Tower3, Tower2, n - 1);
) until it satisfies a condition(if (n == 1))

Posted 4-Feb-14 19:47pm

Prasad Avunoori

Comments

Member 10540766 5-Feb-14 2:09am

I understand that it is calling itself over and over until the conditions are met, but i am trying to understand if:

Hanoi(1, 2, 3, 3);

means that n = 1 then 2 then 3 then 3.
Or if its
Hanoi(int Tower1, int Tower2, int Tower3, int n)
Hanoi(1, 2, 3, 3);

Meaning that tower1 = 1, tower2 = 2, tower3 = 3, n = 3 ?

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CoderPanda · Accepted Answer · 2014-02-04T19:54:00

First of all, thanks for asking an intellectual question. Don't get to see these often and I, personally, absolutely love to talk about these. I would like you to understand it yourself and I am sure you can. I will only explain the code a bit more to help you out.

(Assuming you know what a Tower of Hanoi[^] puzzle is...)

In short - Recursion means invoking itself. Or the repeated application of the same procedure on itself.

In your example, the method Hanoi is invoking itself for certain number of times and eventually
solving itself[^] which is why it is a recursive procedure or method.

In your code, Towers are the rods and n(=3) is the number of discs. Here is the logic your code follows every time the Hanoi method is called:
To move n discs from Tower 1 to Tower 3
move n−1 discs from Tower 1 to Tower 2. This leaves disc n alone on Tower 1.
move disc n from Tower 1 to Tower 3
move n−1 discs from Tower 2 to Tower 3 so they sit on disc n

Now go ahead and put a break point in Hanoi() and keep doing F10 until you understand it. Put watches on Tower1, Tower2, Tower3 and n which will help you.

If stuck, write back. Happy Coding.

Also, if you are a lover of programming puzzles like me, please see this[^]

[Please accept/up-vote answers or solutions that work for you to encourage others]

Trying to understand recursion better

3 solutions

Solution 2

Solution 3

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us