/*

    Recurse.java
    CIS 160
    David Klick
    11/12/04

    This program demonstrates various recursion algorithms.
*/

public class Recurse {
    public static void main(String[] args) {

        // test recursive factorial method
        System.out.println("N       N!");
        for (long i=0; i<10; i++) {
            System.out.println(i + "\t" + fact(i));
        }
        System.out.println();

        // test recursive Fibonacci method
        System.out.println("n       fib(n)");
        for (long i=0; i<10; i++) {
            System.out.println(i + "\t" + fib(i));
        }
        System.out.println();

        // test recursive solution to Towers of Hanoi puzzle
        System.out.println("Moving 4 disks from peg 1 to peg 3");
        moveDisks(4, 1, 3);

    }

    // calculates the factorial of a number
    private static long fact(long n) {
        if (n < 2) return 1;
        else return n * fact(n-1);
    }

    // calculates a particular Fibonacci number
    private static long fib(long n) {
        if (n < 2) return n;
        else return fib(n-1) + fib(n-2);
    }

    // displays moves needed to complete the Tower of Hanoi puzzle
    private static void moveDisks(int numDisks, int src, int dest) {
        // check for invalid peg numbers (only allow 1, 2, 3)
        if (src < 1 || src > 3 || dest < 1 || dest > 3) {
            System.out.println("Error: peg numbers are invalid");
            return;
        }

        // check for invalid peg numbers (src and dest must be different)
        if (src == dest) {
            System.out.println("Error: peg numbers are the same");
            return;
        }

        // check for invalid number of disks (must be >= 1)
        if (numDisks < 1) {
            System.out.println("Error: invalid number of disks");
            return;
        }

        // if moving 1 disk, answer is obvious
        if (numDisks == 1) {
            System.out.println("move disk from peg " + src
                + " to peg " + dest);
        } else {
            int thirdPeg = (1 + 2 + 3) - src - dest;
            moveDisks(numDisks-1, src, thirdPeg);
            moveDisks(1, src, dest);
            moveDisks(numDisks-1, thirdPeg, dest);
        }

    }
}