how to solve the tower of hanoi by recursion versus simulated call stack?

 
/*
   TowerOfHanoi.java  遞迴版 及 模擬呼叫堆疊版 求解河內塔 
 
> java TowerOfHanoi
Hanoi Tower by Implicit Call Stack 遞迴版
A:[3, 2, 1], B:[], C:[]		1: Move disk 1 from A to C
        A:[3, 2], B:[], C:[1]		2: Move disk 2 from A to B
        A:[3], B:[2], C:[1]		3: Move disk 1 from C to B
A:[3], B:[2, 1], C:[]		4: Move disk 3 from A to C
A:[], B:[2, 1], C:[3]		5: Move disk 1 from B to A
        A:[1], B:[2], C:[3]		6: Move disk 2 from B to C
        A:[1], B:[], C:[3, 2]		7: Move disk 1 from A to C
A:[], B:[], C:[3, 2, 1]
 
Hanoi Tower by Explicit Stack 模擬呼叫堆疊版
A:[3, 2, 1], B:[], C:[]		1: Move disk 1 from A to C
        A:[3, 2], B:[], C:[1]		2: Move disk 2 from A to B
        A:[3], B:[2], C:[1]		3: Move disk 1 from C to B
A:[3], B:[2, 1], C:[]		4: Move disk 3 from A to C
A:[], B:[2, 1], C:[3]		5: Move disk 1 from B to A
        A:[1], B:[2], C:[3]		6: Move disk 2 from B to C
        A:[1], B:[], C:[3, 2]		7: Move disk 1 from A to C
A:[], B:[], C:[3, 2, 1]
*/
import java.util.Stack;
 
public class TowerOfHanoi 
{
    static Stack stackA = new Stack<>();  // 柱A
    static Stack stackB = new Stack<>();  // 柱B
    static Stack stackC = new Stack<>();  // 柱C
    static int nDisks = 5; // Number of disks 盤數
    static int count = 0;  // 步數
    static boolean printGoal = false;  // 列印目標否
    static boolean printOperation = true;  // 列印步驟否
    static boolean printStack = false;  // 列印模擬呼叫堆疊否
    // 印n格空白
    public static void printSpaces(int n)
    {
        for(int i=0; i <= n -1; i++) System.out.print(" ");
    }
    
    // 印柱A,柱B,柱C堆疊,前面n層內縮
    public static void printStacks(int n)
    {
        StringBuilder sb = new StringBuilder();
        sb.append("A:" + stackA);
        sb.append(", B:" + stackB);
        sb.append(", C:" + stackC);
        System.out.println();
        printSpaces(n*8);  // 每層內縮8格
        System.out.print(sb.toString());
    }
    
    // 搬移柱from頂一個盤子到柱to
    public static void transfer(char from, char to)
    {
        if(from=='A' && to=='B') stackB.push(stackA.pop());
        if(from=='A' && to=='C') stackC.push(stackA.pop());
        if(from=='B' && to=='A') stackA.push(stackB.pop());
        if(from=='B' && to=='C') stackC.push(stackB.pop());
        if(from=='C' && to=='A') stackA.push(stackC.pop());
        if(from=='C' && to=='B') stackB.push(stackC.pop());
    }
    
    // 遞迴版解河內塔，將n個盤子從柱sourc，搬到柱target，透過柱auxiliary
    public static void solveHanoi(int n, char source, char auxiliary, char target) 
    {        
        if(printGoal) 
        {
            System.out.println();
            printSpaces((nDisks - n)*8);
            System.out.print(String.format("hanoi(n:%d,s:%c -> t:%c)",n,source,target));
        }
        if (n == 1) 
        {
            if(printOperation) 
                System.out.print(String.format("\t\t%d: Move disk 1 from %c to %c", ++count, source, target));
            transfer(source, target);            
        } 
        else 
        {
            solveHanoi(n - 1, source, target, auxiliary);
            printStacks(nDisks - n);            
            if(printOperation) 
                System.out.print(String.format("\t\t%d: Move disk %d from %c to %c", ++count, n, source, target));
            transfer(source, target);
            printStacks(nDisks - n);
            solveHanoi(n - 1, auxiliary, source, target);
        }
    }
    // 模擬呼叫記錄    
    static class HanoiCallRecord
    {
        int num;
        char source;
        char auxiliary;
        char target;
        int stage; // 0 for moving n-1 disks from source to auxiliary rods; 
                   // 1 for moving the disk n from source to target rods
                   //   and moving n-1 disks from auxiliary to target rods
                   // 2 for backtracking to the previous call record
        
        // 建構子
        public HanoiCallRecord(int num, char source, char auxiliary, char target)
        {
            this.num = num;
            this.source = source;
            this.auxiliary = auxiliary;
            this.target = target;
            this.stage = 0;  // 預設從階段0開始
        }
        
        // 列印呼叫記錄
        public String toString()
        {
            return String.format("(n:%d,s:%c,a:%c,t:%c,s:%d)",
                    num, source, auxiliary, target, stage);
        }
    }
    
    // 模擬呼叫堆疊，解河內塔，將n個盤子從柱sourc，搬到柱target，透過柱auxiliary
    public static void hanoiUsingStacks(int num, char src, char aux, char tgt) 
    {
        Stack stack = new Stack<>();
        
        HanoiCallRecord initial = new HanoiCallRecord(num, src, aux, tgt);
        stack.push(initial);  // 壓入第1層呼叫記錄
        while (stack.isEmpty()==false) 
        {
            if(printStack) System.out.print("\n" + stack);
            
            HanoiCallRecord current = stack.peek();  // 檢視本層呼叫記錄
            int n = current.num;
            char source = current.source;
            char auxiliary = current.auxiliary;
            char target = current.target;
            int stage = current.stage;
            
           if (n == 1) // 執行特別任務，然後退回上一層任務
           {
                if(printOperation) 
                    System.out.print(String.format("\t\t%d: Move disk 1 from %c to %c", ++count, source, target));
                transfer(source, target);
                stack.pop();  // 彈出本層呼叫記錄,
            } 
            else if(stage == 0) // 階段0, 執行本層第0階段任務
            {
                // solveHanoi(n - 1, source, target, auxiliary);
                HanoiCallRecord next = new HanoiCallRecord(n - 1, source, target, auxiliary);
                stack.push(next); // 壓入下層呼叫記錄
                current.stage++;  // 更新本層呼叫記錄的階段欄位
            }
            else if(stage == 1) // 階段1, 執行本層第1階段任務
            {
                printStacks(nDisks - n);            
                if(printOperation)
                    System.out.print(String.format("\t\t%d: Move disk %d from %c to %c", ++count, n, source, target));
                transfer(source, target);
                printStacks(nDisks - n);
                // solveHanoi(n - 1, auxiliary, source, target);
                HanoiCallRecord next = new HanoiCallRecord(n - 1, auxiliary, source, target);
                stack.push(next);  // 壓入下層呼叫記錄
                current.stage++; // 更新本層呼叫記錄的階段欄位
            }
            else if(current.stage == 2) // 階段2,本層任務完成,退回上一層任務
            {
                stack.pop();  // 彈出本層呼叫記錄,
            }
        }
    } 
    // 測試主程式
    public static void main(String[] args) 
    {
        nDisks = 3; // Number of disks
        count = 0;
        for(int i=nDisks; i >= 1; i--) stackA.push(i);
        
        System.out.print("Hanoi Tower by Implicit Call Stack 遞迴版");
        printStacks(0);
        solveHanoi(nDisks, 'A', 'B', 'C');
        printStacks(0);
        
        // ===================================
    
        count = 0;
        stackA.clear();
        stackB.clear();
        stackC.clear();
        for(int i=nDisks; i >= 1; i--) stackA.push(i);
                    
        System.out.print("\n\nHanoi Tower by Explicit Stack 模擬呼叫堆疊版");
        
        printStacks(0);
        hanoiUsingStacks(nDisks, 'A', 'B', 'C');
        printStacks(0);
    }
}