h

/*
Recursion
02/20/18
 */
package javaapplication2;

import java.util.Scanner;

public class JavaApplication2 {

    /*
    Returns factorial for given n
    0! = 1
    1! = 1
    2! = 2
    3! = 6
     */
    static int getFactIter(int n) {
        int fact = 1;
        for (int i = 2; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }

    /*
     Recursive method for above method
     n! = (n-1)!*n
     */
    static int getFact(int n) {

        if (n == 0) {
            System.out.println();
            return 1;
        }

        return getFact(n - 1) * n;
    }

    /*
     Summation
     1+2+3+4+...+n
     */
    static int getSum(int n) {

        if (n == 1) {
            return 1;
        }
        return getSum(n - 1) + n;
    }

    /*
     If given n = 12345
     return 15
     */
    static int getDigitSum(int n) {
        if (n == 0) {
            return 0;
        }
        return getDigitSum(n / 10) + n % 10;
    }

    // Goes through recursive method one less time than getDigitSum
    static int getDigitSum1(int n) {
        if (n < 10) {
            return n;
        }
        return getDigitSum(n / 10) + n % 10;
    }

    /*
     Reverse string s
      s = abcde
      r = edcba
     */
    static String reverse(String s) {
        if (s.length() == 1) {
            return s;
        }
        return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));
    }

    // Faster reverse
    static String reverse1(String s) {
        if (s.length() == 1) {
            return s;
        }
        return s.charAt(s.length() - 1) + reverse(s.substring(1, s.length() - 1)) + s.charAt(0);
    }

    /*
     b^n
     2^n = 2^(n-1)*2, 2^0 = 1
     Same as inducion proofs in 195
     */
    // Count Var to see which is faster
    static int cnt1 = 0;

    static int getPow(int b, int n) {
        cnt1++;
        if (n == 0) {
            return 1;
        }
        return getPow(b, n - 1) * b;
    }

    /*
     2^10, 2^9, 2^8, ... 1

    Quicker way:
    Even power:
        2^16 = 2^8 * 2^8,
        2^8  = 2^4 * 2^4,
        2^4  = 2^2 * 2^2,
        2^2  = 2   * 2

    Odd Power:
        2^14 = 2^7 * 2^7
        2^7  = 2^3 * 2^3 * 2
     */
    // Count Var to see which is faster
    static int cnt2 = 0;

    static int getPowFaster(int b, int n) {
        cnt2++;
        if (n == 0) {
            return 1;
        }
        int t = getPowFaster(b, n / 2);
        if (n % 2 == 0) {
            return t * t;
        }
        return t * t * b;
    }

    /*
     Fibonacci numbers
     f(n) = f(n - 1) + f(n - 2)
     f(1) = 1
     f(2) = 1
     */
    static int getFibo(int n) {
        if(n <= 2)
            return 1;
        return getFibo(n - 2) + getFibo(n - 1);
    }

    // Tower of Hanoi
    static void towerHanoi(int n, char p1, char p2, char p3) {
        if(n > 0){
            towerHanoi(n - 1, p1, p3, p2);
            System.out.println(p1+" -> "+p3);
            towerHanoi(n - 1, p2, p1, p3);
        }
    }

    public static void main(String[] args) {

//        System.out.println(getPow(2, 20));
//        System.out.println(getPowFaster(2, 20));
//        System.out.println("GetPow: "+cnt1+" | GetPowFaster: "+cnt2);
//        System.out.println(getFibo(8));
          towerHanoi(10, 'A', 'B', 'C'); // 2^ n times

    }
}