Base vs Recursive Case

public static returnType method(parameters) {
    if (base case condition) {
        return base case value;       // STOP — don't recurse
    }
    // do some work
    return ... method(smaller input);  // RECURSE — call yourself
}

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

// WRONG — n never gets closer to the base case!
public static int broken(int n) {
    if (n == 0) return 0;
    return n + broken(n);  // calling with same n — infinite recursion!
}

public static String reverse(String s) {
    if (s.length() <= 1) return s;    // base: empty or single char
    return reverse(s.substring(1)) + s.charAt(0);
}

public static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true;  // base: 0 or 1 chars
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalindrome(s.substring(1, s.length() - 1));
}

public static int countChar(String s, char target) {
    if (s.length() == 0) return 0;
    int match = (s.charAt(0) == target) ? 1 : 0;
    return match + countChar(s.substring(1), target);
}

System.out.println(countChar("mississippi", 's')); // 4

public static int binarySearch(int[] arr, int target, int lo, int hi) {
    if (lo > hi) return -1;               // base case: not found
    
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;     // base case: found!
    
    if (target < arr[mid]) {
        return binarySearch(arr, target, lo, mid - 1);   // search left
    } else {
        return binarySearch(arr, target, mid + 1, hi);   // search right
    }
}

public static int sum(int n) {
    return n + sum(n - 1);  // no base case — StackOverflowError
}

public static int bad(int n) {
    if (n == 0) return 0;   // base case exists but...
    return n + bad(n + 1);  // n goes UP, never reaches 0!
}

public static int good(int n) {
    if (n == 0) return 0;   // base case
    return n + good(n - 1); // n goes DOWN toward 0 ✓
}

public class RecursiveArrays {
    // Sum all elements starting from index
    public static int sum(int[] arr, int index) {
        if (index == arr.length) return 0;  // base: past the end
        return arr[index] + sum(arr, index + 1);
    }
    
    // Find maximum starting from index
    public static int max(int[] arr, int index) {
        if (index == arr.length - 1) return arr[index]; // base: last element
        int restMax = max(arr, index + 1);
        return Math.max(arr[index], restMax);
    }
    
    // Check if array contains target
    public static boolean contains(int[] arr, int target, int index) {
        if (index == arr.length) return false;  // base: exhausted array
        if (arr[index] == target) return true;   // base: found it
        return contains(arr, target, index + 1);
    }
    
    public static void main(String[] args) {
        int[] nums = {3, 7, 1, 9, 4};
        System.out.println("Sum: " + sum(nums, 0));         // 24
        System.out.println("Max: " + max(nums, 0));         // 9
        System.out.println("Has 7: " + contains(nums, 7, 0)); // true
        System.out.println("Has 5: " + contains(nums, 5, 0)); // false
    }
}