//demo of recursion

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;
    }

    //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
        }
    }

    public static void main(String[] args) {
	// write your code here
        System.out.println("Sum from 1 to 100 is " + algSumRecursion(100));
        System.out.println("Sum from 1 to 100 is " + algSumLoop(100));

        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));
    }
}