I think every one of you knows the tower of hanoi. You have three rods and three or more disks of different sizes. The objective is to move every disks to the third rod, but you can’t put a bigger disk onto a smaller disk.
Our professor taught us, that methods in java can be recursive and he used an example which solved the tower of hanoi with “n” disks.
This was really fast and you have to really think about it to understand how it works. I’ll try to help you out.
public static void tower(int n){
}
This is the method we will use.
- “static” means we won’t need to create an object for using this method.
- “void” means it doesn’t return anything
- the parameter “n” says how many disks the tower has
I will name the first rod “one”, the second “two”, and the third “three”.
How do we start?
0 DISKS:
If we have 0 disks, we can’t move anyone. So we need to check if n is greater than 0:
public static void tower(int n){
if (n > 0){
}
}
1 DISK:
One disk we can easily move to road three to accomplish our goal. So we do:
public static void tower(int n){
if (n > 0){
System.out.println("1 --> 3");
}
}
Okay, our method know is working for “n<=0" and "n=1", but for "n=2" we get the same message. So that's where the recursive part comes.. 2 DISKS:
This is what we need to do with two disks:
1 --> 2 1 --> 3 2 --> 3
Right?
We actually have the “1 –> 3” part. So we know that we need something before and after it.
public static void tower(int n){
if (n > 0){
//for n=2: 1-->2
System.out.println("1 --> 3");
//for n=2: 2-->3
}
}
Before “System.out.println(“1 –> 3″);” we call tower(n) again, but we will get get a problem:
When we call this method again, it will do exactly the same. So in this case if we call tower(n) again we will get an endless loop..
- At first instead of “n” we will use “n-1” because everytime we moved one disk to “2” or “3” we have “n-1” disks on rod “1” left.
- In “System.out.println(“1 –> 3″);” we have to replace “1” and “3” with a variable so that we can later display “1 –> 2” or “2–>3”. I’ll use two integer variables called “one” and “three”
- The next thing is, if we call the tower before “System.out.println(“1 –> 3″);” again, the method need to know that the disk should be moved like “1 –> 2” instead of “1 –> 3”. So we need to add 3 parameters for the different rods.
This looks like:
public static void tower(int n, int one, int two, int three){
if (n > 0){
//for n=2: 1-->2
System.out.println(one + " --> " + three);
//for n=2: 2-->3
}
}
Now if you call tower(1, 1, 2, 3) you’ll get: “1 –> 3”.
What does that mean? If you have only one disk left: the second parameter defines the origin and the fourth parameter where the disk goes.
So we remember: If we call tower(2, 1, 2, 3) the first output we need is “1–>2”. So we call tower(n-1, one, three, two); Just before “System.out.println(…)”
public static void tower(int n, int one, int two, int three){
if (n > 0){
tower(n-1, one, three, two);
System.out.println(one + " --> " + three);
//for n=2: 2-->3
}
}
Why do i changed “two” and “three”?
We call tower with "n=2" n=2: n is greater than zero n=2: we call tower again with "n-1" which is "n=1" and we swapped the parameter "two" for "three" n=1: n is greater than zero n=1: we call tower again with "n-1" which is "n=0" n=0: n is not greater than zero n=1: System.out.println(one + " --> " + three) => here we expect "1 -- > 2"! (remember, we swapped "two" for "three") n=2: System.out.println(one + " --> " + three) => here we expect "1 -- > 3"!
The output we get is:
1 --> 2 1 --> 3
Now only “2 –> 3” is missing. So we have to swap “two” for “one”:
public static void tower(int n, int one, int two, int three){
if (n > 0){
tower(n-1, one, three, two);
System.out.println(one + " --> " + three);
tower(n-1, two, one, three);
}
}
So again:
We call tower with "n=2" n=2: n is greater than zero n=2: we call tower again with "n-1" which is "n=1" and we swapped the parameter "two" for "three" n=1: n is greater than zero n=1: we call tower again with "n-1" which is "n=0" n=0: n is not greater than zero n=1: System.out.println(one + " --> " + three) => here we expect "1 -- > 2"! (remember, we swapped "two" for "three") n=1: we call tower with "n-1" which is "n=0" n=0: n is not greater than zero n=2: System.out.println(one + " --> " + three) => here we expect "1 -- > 3"! n=2: we call tower again with "n-1" which is "n=1" and we swapped the parameter "two" for "one" n=1: we call tower again with "n-1" which is "n=0" n=0: n is not greater than zero n=1: System.out.println(one + " --> " + three) => here we expect "2 -- > 3"! (remember, we swapped "one" for "two") n=1: we call tower with "n-1" which is "n=0" n=0: n is not greater than zero
We tested it with an odd number (1) and an even number (2). If n is a odd number the first and last line will always be “1 — > 3”. With even numbers the first line will always be “1 — > 2” and the last line will always be “2 — > 3”. This will work for n > 0.
I hope you got it.