Recursion — Think Like a Computer

public void countdown(int n) {
    if (n <= 0) {        // base case
        System.out.println("Done!");
        return;
    }
    System.out.println(n);
    countdown(n - 1);    // recursive case
}

public int factorial(int n) {
    if (n == 0) return 1;        // base case
    return n * factorial(n - 1); // recursive case
}
 
// factorial(3)
// = 3 * factorial(2)
// = 3 * 2 * factorial(1)
// = 3 * 2 * 1 * factorial(0)
// = 3 * 2 * 1 * 1 = 6

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

public int fib(int n) {
    return fibMemo(n, new HashMap<>());
}
 
private int fibMemo(int n, Map<Integer, Integer> memo) {
    if (memo.containsKey(n)) return memo.get(n);
    if (n <= 1) return n;
    
    int result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, result);
    return result;
}

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);      // sort left half
    mergeSort(arr, mid + 1, right); // sort right half
    merge(arr, left, mid, right);   // combine
}

public void inorder(TreeNode node) {
    if (node == null) return;     // base case
    inorder(node.left);           // left subtree
    System.out.println(node.val); // process
    inorder(node.right);          // right subtree
}

public void permutations(int[] arr, List<Integer> current, boolean[] used) {
    if (current.size() == arr.length) {
        System.out.println(current);
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        if (!used[i]) {
            used[i] = true;
            current.add(arr[i]);         // choose
            permutations(arr, current, used);
            current.remove(current.size() - 1); // undo (backtrack)
            used[i] = false;
        }

// Not tail recursive — multiplication happens after return
public int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1); // multiply after recursive call
}
 
// Tail recursive — accumulator carries the result
public int factorialTail(int n, int acc) {
    if (n == 0) return acc;
    return factorialTail(n - 1, n * acc); // last operation is the call
}