import java.util.ArrayList;
import java.util.List;

public class Recursion {

	public static int sum(int n) {
		int total = 0;
		if (n == 1) {
			// base case
			total = 1;
		} else {
			// recursive call
			total = n + Recursion.sum(n - 1);
		}
		return total;
	}

	public static long factorial(int n) {
		long total = 0;
		if (n == 1) {
			// base case
			total = 1;
		} else {
			// recursive call
			total = n * Recursion.factorial(n - 1);
		}
		return total;
	}

	public static boolean isPrime(int x, int divisor) {
		boolean result = false;
		if (divisor > Math.sqrt(x)) {
			// base case, you don't have to check any divisor greater
			// than sqrt(x) because sqrt(x) * sqrt(x) == x
			result = true;
		} else if (divisor > 1 && x % divisor == 0) {
			// another base case, here we've found a divisor
			// that divides evenly into x
			result = false;
		} else {
			// recursively try the next divisor
			result = Recursion.isPrime(x, divisor + 1);
		}
		return result;
	}

	public static String reverse(String s) {
		String rev = "";
		if (s.length() < 2) {
			// base case
			rev = s;
		} else {
			// recursive call
			int lastIndex = s.length() - 1;
			char lastChar = s.charAt(lastIndex);
			String sMinusLast = s.substring(0, lastIndex); // s minus the last character
			rev = lastChar + Recursion.reverse(sMinusLast);
		}
		return rev;
	}

	public static String everySecondChar(String s, int idx) {
		String result = "";
		if (idx >= s.length()) {
			// base case
			result = "";
		} else {
			// at the character at the current index to the front of the result
			char cIdx = s.charAt(idx);
			
			// recursively concatenate every second char in the rest of the string
			result = cIdx + Recursion.everySecondChar(s, idx + 2);
		}
		return result;
	}

	public static int sumEven(List<Integer> t) {
		int sum = 0;
		if (t.isEmpty()) {
			// base case
			sum = 0;
		} else {
			// look at the first element and check if it is even
			Integer first = t.get(0);
			if (first % 2 == 0) {
				// first element is even, add it to the sum
				sum = first;
			}
			// recursively sum the even numbers in the rest of the list
			sum += Recursion.sumEven(t.subList(1, t.size()));
		}
		return sum;
	}

	public static List<Integer> allEven(List<Integer> t) {
		List<Integer> result = new ArrayList<Integer>();
		if (t.isEmpty()) {
			// do nothing, there are no integers in t
		} else {
			// look at the first element and check if it is even
			Integer first = t.get(0);
			if (first % 2 == 0) {
				// first element is even, add it to the list
				result.add(first);
			}
			// recursively add the even numbers in the rest of the list
			// note the use of addAll here
			result.addAll(Recursion.allEven(t.subList(1, t.size())));
		}
		return result;
	}
	
	public static String everySecond(List<String> t, int idx) {
		String result = "";
		if (idx >= t.size()) {
			// base case
			result = "";
		} else {
			// add the string at the current idx to the front of the result
			String sIdx = t.get(idx);
			
			// recursively concatenate every second string in the rest of the list
			result = sIdx + Recursion.everySecond(t, idx + 2);
		}
		return result;
	}


}