Recursion

1// Classic: Factorial (n! = n * (n-1)!)
2public int factorial(int n) {
3    // Base case
4    if (n <= 1) {
5        return 1;
6    }
7    // Recursive case
8    return n * factorial(n - 1);
9}
10
11// Trace: factorial(5)
12// 5 * factorial(4)
13// 5 * 4 * factorial(3)
14// 5 * 4 * 3 * factorial(2)
15// 5 * 4 * 3 * 2 * factorial(1)
16// 5 * 4 * 3 * 2 * 1 = 120
17
18System.out.println(factorial(5));  // 120
19System.out.println(factorial(0));  // 1

1// Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13...
2public int fibonacci(int n) {
3    if (n <= 1) return n;  // Base cases: fib(0)=0, fib(1)=1
4    return fibonacci(n - 1) + fibonacci(n - 2);
5}
6
7// WARNING: Naive Fibonacci is O(2^n) - very slow!
8// Use memoization or iteration for large n
9
10// Memoized Fibonacci (much faster!)
11private Map<Integer, Integer> memo = new HashMap<>();
12
13public int fibMemo(int n) {
14    if (n <= 1) return n;
15    if (memo.containsKey(n)) return memo.get(n);
16    
17    int result = fibMemo(n - 1) + fibMemo(n - 2);
18    memo.put(n, result);
19    return result;
20}

1// Sum of array elements recursively
2public int sumArray(int[] arr, int index) {
3    if (index >= arr.length) return 0;  // Base case
4    return arr[index] + sumArray(arr, index + 1);
5}
6
7// Binary search recursively
8public int binarySearch(int[] arr, int target, int left, int right) {
9    if (left > right) return -1;  // Not found
10    
11    int mid = left + (right - left) / 2;
12    
13    if (arr[mid] == target) return mid;
14    else if (arr[mid] > target)
15        return binarySearch(arr, target, left, mid - 1);
16    else
17        return binarySearch(arr, target, mid + 1, right);
18}
19
20// String reversal
21public String reverse(String str) {
22    if (str.isEmpty()) return str;
23    return reverse(str.substring(1)) + str.charAt(0);
24}
25
26System.out.println(reverse("hello")); // "olleh"

1// Tower of Hanoi - classic recursive algorithm
2public void towerOfHanoi(int n, char from, char to, char aux) {
3    if (n == 1) {
4        System.out.println("Move disk 1 from " + from + " to " + to);
5        return;
6    }
7    towerOfHanoi(n - 1, from, aux, to);
8    System.out.println("Move disk " + n + " from " + from + " to " + to);
9    towerOfHanoi(n - 1, aux, to, from);
10}
11
12// Directory traversal (practical use case)
13public void listFiles(File dir, String indent) {
14    if (!dir.exists()) return;
15    
16    System.out.println(indent + dir.getName());
17    
18    if (dir.isDirectory()) {
19        for (File file : dir.listFiles()) {
20            listFiles(file, indent + "  ");
21        }
22    }
23}
24
25// Recursion vs Iteration comparison
26// Iterative factorial (usually preferred)
27public int factorialIterative(int n) {
28    int result = 1;
29    for (int i = 2; i <= n; i++) {
30        result *= i;
31    }
32    return result;
33}