Thursday, March 10, 2005

Recursion

2 Program

Examples of recursive methods to be explained later and compared to iterative methods.

class Recursion {
    public static void main(String[] args) {
        count(10); System.out.println();
        countdown(10); System.out.println();
        System.out.println("factorial(4) = " + factorial(4));
        System.out.println("fibonacci(10) = " + fibonacci(10));
        System.out.println("binC(6, 4) = " + binC(6, 4));
        System.out.println("gcd(378, 45) = " + gcd(378, 45));
        hanoi(3, 'A', 'C', 'B');
    }
    
    public static void count(int n) {
        if (n == 1)
            System.out.print(n);
        else {
            count(n - 1);
            System.out.print(" " + n);
        }
    }

    public static void countdown(int n) {
        if (n == 1)
            System.out.print(n);
        else {
            System.out.print(n + " ");
            countdown(n - 1);
        }
    }

    public static long factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }

    public static long fibonacci(int n) {
        if (n <= 2) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static int binC(int m, int n) {
        if (n == 0 || m == n) {
            return 1;
        } else {
            return binC(m - 1, n) + binC(m - 1, n - 1);
        }
    }

    public static int gcd(int m, int n) {
        if (m % n == 0) {
            return n;
        } else {
            return gcd(n, m % n);
        }
    }

    public static void hanoi(int n, char sourcePeg, char destinationPeg, char auxiliaryPeg) {
        if (n == 1) {
            System.out.println("Move disk " + n + " from peg " + sourcePeg + " to peg " + destinationPeg);
        } else {
            hanoi(n - 1, sourcePeg, auxiliaryPeg, destinationPeg);
            System.out.println("Move disk " + n + " from peg " + sourcePeg + " to peg " + destinationPeg);
            hanoi(n - 1, auxiliaryPeg, destinationPeg, sourcePeg);
        }
    }
}

No comments: