Abdullah Khan Abdullah Khan - 2 months ago 7
Java Question

How can I make a list of steps not repeat in a recursive method?

The output of the code is 1,1, 2,2 3,3, 4,4, instead of 1, 2, 3, 4. I tried a lot of different placements for the a variable to make it work, but this is the closest I have gotten it. Am I just misunderstanding something fundamental about recursion?

import java.util.Scanner;

public class TowerOfHanoi {

public static int a = 1;

public static void main(String[] args) {

TowerOfHanoi towerOfHanoi = new TowerOfHanoi();

System.out.println("Enter number of disks: ");

Scanner scan = new Scanner(System.in);
int disks = scan.nextInt();

towerOfHanoi.solve(disks, "1", "2", "3");

scan.close();
}



public void solve(int n, String start, String mid, String end){

if(n == 1){

System.out.println(a + " : "+ start + " to " + end);

a++;

} else {
solve(n-1, start, end, mid);

System.out.println(a + " : " + start + " to " + end);

solve(n-1, mid, start, end);
}
}
}


Output:

Enter number of disks:
3
1 : 1 to 3
2 : 1 to 2
2 : 3 to 2
3 : 1 to 3
3 : 2 to 1
4 : 2 to 3
4 : 1 to 3

Answer

The sequence of steps looks right to me, but you forgot to increment a in the else clause in solve(...).

Solve should look something like this:

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