CODEWITHSUNDEEP
javarecursiontowers-of-hanoi
Gilgamesh Craos
Gilgamesh Craos

Reputation: 15

Why does this Tower of Hanoi program work?

I'm a complete beginner at coding, and I was working on a few simple mini-projects to get more familiar with java. When I encountered this Tower of Hanoi code.

public class TowersOfHanoi {

    public void solve(int n, String start, String auxiliary, String end) {
        if (n == 1) {
            System.out.println(start + " -> " + end);
        } else {
            solve(n - 1, start, end, auxiliary);
            System.out.println(start + " -> " + end);
            solve(n - 1, auxiliary, start, end);
        }
    }

    public static void main(String[] args) {
        TowersOfHanoi towersOfHanoi = new TowersOfHanoi();
        System.out.print("Enter number of discs: ");
        Scanner scanner = new Scanner(System.in);
        int discs = scanner.nextInt();
        towersOfHanoi.solve(discs, "A", "B", "C");
       }
    }

I understand how the puzzle works; however, I can't understand how this code knows where to move the respective pieces of the tower without violating the rule that a larger piece cannot rest atop a smaller one. Additionally, because of my very weak understanding of code, I thought that if (n==1){ was not true then it moves on to the else. But instead of that even when I enter values for n that aren't 1 the code moves to utilize the information directly under the if statement instead of jumping to the else line beneath it.

For example if my scanner input was 4, then the way I previously understood it, the code would set the scanner's input to the int discs and funnel that to the towersOfHanoi.solve(discs,"A", "B", "C");. So wouldn't that mean when the program pulls up the .solve method int n would be equal to 4? And again wouldn't the code check to see if if(n==1){ which it shouldn't...as I thought it would be (4==1).

I do know that this is a recursive solution to the problem, but does that really affect the rules of how java processes the code?

P.S. I apologize if I used any terminology wrong or if I'm not clear enough, I'm teaching myself and so I don't have anyone else to ask my questions... Also I didn't make this code, I found it on a site that had a recursive version of the java source code solution to the puzzle.

Upvotes: 0

Views: 286

Answers (1)

Naman
Naman

Reputation: 31858

I thought that if (n==1){ was not true then it moves on to the else. But instead of that even when I enter values for n that aren't 1 the code moves to utilize the information directly under the if statement

What you thought holds on for your input unless the value of the chained input reduces to 1, because of the following statement, e.g.:-

solve(n - 1, start, end, auxiliary);

Let's say when you provide n =3,

At 1st iteration, control moves to else and calls the same method with 

solve(2, start, end, auxiliary)

At 2nd iteration, it reaches else and calls again with

solve(1, start, end, auxiliary) // and you know this would reach if(n==1) next time

The above iterations are the effect of recursion, wherein you're calling the same method from within with different values. The statement 

if(n==1)

is precisely the tail of your recursion and is a must to exit out of it, hence would always be reached.

Upvotes: 2

Related Questions