5.4. Recursion

Recursion is a programming technique where a method calls itself to solve a problem. Recursive solutions break down complex problems into smaller, similar subproblems.

Basic Recursion Structure

public returnType recursiveMethod(parameters) {
    // Base case - stopping condition
    if (baseCaseCondition) {
        return baseCaseValue;
    }

    // Recursive case - method calls itself
    return recursiveMethod(modifiedParameters);
}

Simple Recursion Examples

Factorial Calculation

public class Factorial {

    /**
     * Calculates factorial of a non-negative integer recursively
     * n! = n * (n-1) * (n-2) * ... * 1
     * 0! = 1
     */
    public static long factorial(int n) {
        // Base case
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
        if (n == 0 || n == 1) {
            return 1;
        }

        // Recursive case
        return n * factorial(n - 1);
    }

    /**
     * Iterative version for comparison
     */
    public static long factorialIterative(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }

        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.println(i + "! = " + factorial(i));
        }

        // Compare recursive and iterative
        System.out.println("5! recursive: " + factorial(5));
        System.out.println("5! iterative: " + factorialIterative(5));
    }
}

Fibonacci Sequence

public class Fibonacci {

    /**
     * Calculates nth Fibonacci number recursively
     * F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
     */
    public static long fibonacci(int n) {
        // Base cases
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
        if (n == 0) return 0;
        if (n == 1) return 1;

        // Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    /**
     * Optimized version with memoization to avoid repeated calculations
     */
    public static long fibonacciMemoized(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }

        long[] memo = new long[n + 2]; // +2 to handle n=0 and n=1
        memo[0] = 0;
        memo[1] = 1;

        return fibonacciMemoized(n, memo);
    }

    private static long fibonacciMemoized(int n, long[] memo) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        // If not calculated yet, calculate and store
        if (memo[n] == 0) {
            memo[n] = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo);
        }

        return memo[n];
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci sequence (first 15 numbers):");
        for (int i = 0; i < 15; i++) {
            System.out.print(fibonacci(i) + " ");
        }
        System.out.println();

        // Compare performance
        int n = 40;
        long startTime = System.currentTimeMillis();
        long result1 = fibonacci(n);
        long time1 = System.currentTimeMillis() - startTime;

        startTime = System.currentTimeMillis();
        long result2 = fibonacciMemoized(n);
        long time2 = System.currentTimeMillis() - startTime;

        System.out.println("Fibonacci(" + n + ") = " + result1);
        System.out.println("Recursive time: " + time1 + "ms");
        System.out.println("Memoized time: " + time2 + "ms");
    }
}

Advanced Recursion Examples

Binary Search Recursively

public class BinarySearch {

    /**
     * Performs binary search recursively on a sorted array
     * @param array sorted array to search in
     * @param target value to find
     * @return index of target, or -1 if not found
     */
    public static int binarySearch(int[] array, int target) {
        return binarySearch(array, target, 0, array.length - 1);
    }

    private static int binarySearch(int[] array, int target, int left, int right) {
        // Base case: search space is empty
        if (left > right) {
            return -1;
        }

        // Calculate middle index
        int mid = left + (right - left) / 2;

        // Base case: target found
        if (array[mid] == target) {
            return mid;
        }

        // Recursive cases: search left or right half
        if (array[mid] > target) {
            return binarySearch(array, target, left, mid - 1); // Search left
        } else {
            return binarySearch(array, target, mid + 1, right); // Search right
        }
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 11;

        int index = binarySearch(sortedArray, target);
        if (index != -1) {
            System.out.println("Found " + target + " at index " + index);
        } else {
            System.out.println(target + " not found in array");
        }
    }
}

Directory Traversal

import java.io.File;

public class DirectoryTraversal {

    /**
     * Recursively lists all files in a directory and its subdirectories
     */
    public static void listFiles(File directory) {
        listFiles(directory, 0);
    }

    private static void listFiles(File directory, int depth) {
        // Base case: if it's not a directory or doesn't exist
        if (!directory.exists() || !directory.isDirectory()) {
            return;
        }

        File[] files = directory.listFiles();
        if (files == null) return;

        for (File file : files) {
            // Print indentation based on depth
            for (int i = 0; i < depth; i++) {
                System.out.print("  ");
            }

            if (file.isDirectory()) {
                System.out.println("[DIR] " + file.getName());
                // Recursive call for subdirectory
                listFiles(file, depth + 1);
            } else {
                System.out.println("[FILE] " + file.getName() + " (" + file.length() + " bytes)");
            }
        }
    }

    public static void main(String[] args) {
        File currentDir = new File(".");
        System.out.println("Directory structure of: " + currentDir.getAbsolutePath());
        listFiles(currentDir);
    }
}

Recursion with Backtracking

N-Queens Problem

public class NQueens {

    /**
     * Solves the N-Queens problem using backtracking
     * Places N queens on an N×N chessboard so no two queens threaten each other
     */
    public static void solveNQueens(int n) {
        int[] board = new int[n]; // board[i] = column of queen in row i
        if (solveNQueens(board, 0, n)) {
            printSolution(board, n);
        } else {
            System.out.println("No solution exists for " + n + " queens");
        }
    }

    private static boolean solveNQueens(int[] board, int row, int n) {
        // Base case: all queens placed
        if (row == n) {
            return true;
        }

        // Try placing queen in each column of current row
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col; // Place queen

                // Recursively place rest of queens
                if (solveNQueens(board, row + 1, n)) {
                    return true;
                }

                // Backtrack: remove queen (implicit in next iteration)
            }
        }

        return false; // No safe column found
    }

    private static boolean isSafe(int[] board, int row, int col) {
        // Check if no queen threatens this position
        for (int i = 0; i < row; i++) {
            // Same column or same diagonal
            if (board[i] == col ||
                Math.abs(board[i] - col) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }

    private static void printSolution(int[] board, int n) {
        System.out.println("Solution for " + n + " queens:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        solveNQueens(4);
        System.out.println();
        solveNQueens(8);
    }
}

Recursion Best Practices

1. Always have a base case: Prevents infinite recursion
2. Make progress toward base case: Each call should reduce the problem size
3. Trust the recursion: Assume recursive calls work correctly
4. Consider stack overflow: Deep recursion may cause StackOverflowError
5. Use memoization: Cache results for expensive recursive calls
6. Know when to use iteration: Some problems are better solved iteratively

public class RecursionGuidelines {

    // Good recursion: clear base case, progress toward base case
    public static int sum(int n) {
        // Base case
        if (n <= 0) return 0;
        // Progress: n decreases by 1 each call
        return n + sum(n - 1);
    }

    // Bad recursion: no clear progress toward base case
    public static void badRecursion(int n) {
        if (n <= 0) return;
        // This doesn't necessarily progress toward base case
        badRecursion(n); // Infinite recursion!
    }

    // Tail recursion (can be optimized by compiler)
    public static int factorialTailRecursive(int n) {
        return factorialTailRecursive(n, 1);
    }

    private static int factorialTailRecursive(int n, int accumulator) {
        if (n <= 1) return accumulator;
        // Tail call: recursive call is the last operation
        return factorialTailRecursive(n - 1, n * accumulator);
    }
}