// more demo of recursion
// Recursion
// 1. Show the stack overflow caused by recursion
// 2. demo: factorial
// 3. demo: Fibinacci
// 4. demo: greatest common divisor


import java.util.*;
public class Main {

    //sum from 1 to n: i.e., sum = 1+2+3+...+n
    public static int algSumRecursion(int n){
        if(n <= 0) return 0; //base case
        return algSumRecursion(n-1) + n; //recursive case
    }

    public static int algSumLoop(int n) {
        int s = 0;
        for (int i = 1; i <= n; ++i) {
            s += i;
        }
        return s;
    }

    public static int factorialLoop(int n){
        int product = 1;
        for (int i = 1; i <= n; ++i) {
            product *= i;
        }
        return product;
    }

    public static int factorialRecursion(int n){
        if(n <= 1) return 1; //base case
        return factorialRecursion(n-1) * n; //recursive case
    }


    //Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
    public static int fibonacciLoop(int n) {
        if (n <= 0) return 0;
        int pre = 0;
        int cur = 1;
        int temp;
        for (int i = 1;  i < n; ++i) {
            temp = pre + cur;
            pre = cur;
            cur = temp;
        }
        return cur;
    }

    public static int fibonacciRecursion(int n) {
        if (n <= 0) return 0; //base case 0
        if (n == 1) return 1; //base case 1
        return fibonacciRecursion(n-2) + fibonacciRecursion(n-1);
    }

    //binary search (recursion), return the index or -1
    public static int binarySearch(ArrayList<Integer> sortedList, int leftIndex, int rightIndex, int key) {
        int midIndex = leftIndex + (rightIndex - leftIndex)/2; // comparing to (leftIndex + rightIndex)/2
        if(leftIndex > rightIndex) return -1; // base case
        if(key == sortedList.get(midIndex)) return midIndex; //base case
        if(key < sortedList.get(midIndex)) {
            return binarySearch(sortedList, leftIndex, midIndex - 1, key); //recursive case
        }
        else {
            return binarySearch(sortedList, midIndex + 1, rightIndex, key); //recursive case
        }
    }

    // greatest common divisor: gcd(12, 21) = 3
    // Euclid algorithm (a > b): gcd(a, b) = gcd(b, a%b)
    public static int gcd(int a, int b) {
        //pre-processing
        if(a < 0) a = -a;
        if(b < 0) b = -b;
        if(a < b) { //exchange a and b
            int temp = a;
            a = b;
            b = temp;
        }

        //base case
        if(b == 0) return a;

        //recursive case
        return gcd(b, a%b);
    }

    public static void main(String[] args) {
	    // test sum. Will see stack overflow with parameter 1000000 or bigger.
        System.out.println("Sum from 1 to 1,000 is " + algSumLoop(1000));
        System.out.println("Sum from 1 to 1,000 is " + algSumRecursion(1000));

        // test factorial
        System.out.println("Factorial of 10 is " + factorialLoop(10));
        System.out.println("Factorial of 10 is " + factorialRecursion(10));

        // test fibonacci
        System.out.println("The 7th Fibonacci number is " + fibonacciLoop(7));
        System.out.println("The 7th Fibonacci number is " + fibonacciRecursion(7));

        // test Euclid's gcd
        System.out.println("GCD(24, 56) is " + gcd(24, 56));

        Integer[] a = {1, 3, 5, 8, 12, 15, 20};
        ArrayList<Integer> myList = new ArrayList<Integer>(Arrays.asList(a));
        System.out.println("Integer 8 is at index " + binarySearch(myList, 0, 6, 8));
    }
}