Introduction to Recursion

Recursion Fundamentals

Classic Recursion Problems

Recursion vs Iteration

Factorial Implementation

public class Factorial {
    public static int factorial(int n) {
        // Base case: factorial of 0 or 1 is 1
        if (n == 0 || n == 1) {
            return 1;
        }
        
        // Recursive case: n! = n * (n-1)!
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("Factorial of 5: " + factorial(5)); // Output: 120
        System.out.println("Factorial of 10: " + factorial(10)); // Output: 3628800
    }
}

Fibonacci Sequence

public class Fibonacci {
    public static int fibonacci(int n) {
        // Base cases: first two Fibonacci numbers
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        // Recursive case: F(n) = F(n-1) + F(n-2)
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    
    // Optimized version with memoization
    public static int fibonacciOptimized(int n, int[] memo) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        // If we've already calculated this value, return it
        if (memo[n] != 0) {
            return memo[n];
        }
        
        // Calculate and store the result
        memo[n] = fibonacciOptimized(n - 1, memo) + fibonacciOptimized(n - 2, memo);
        return memo[n];
    }
    
    public static void main(String[] args) {
        System.out.println("Fibonacci(7): " + fibonacci(7)); // Output: 13
        
        // Using optimized version
        int n = 10;
        int[] memo = new int[n + 1];
        System.out.println("Optimized Fibonacci(10): " + fibonacciOptimized(n, memo)); // Output: 55
    }
}

Guided Practice

For additional hands-on practice and fundamental exercises on recursion, check out our comprehensive guided project:

• Guided Project: Introduction to Recursion

Binary Search - Recursive Implementation

public class RecursiveBinarySearch {
    public static int binarySearch(int[] arr, int target, int left, int right) {
        // Base case: element not found
        if (left > right) {
            return -1;
        }
        
        // Calculate middle index
        int mid = left + (right - left) / 2;
        
        // Base case: element found
        if (arr[mid] == target) {
            return mid;
        }
        
        // Recursive cases
        if (arr[mid] > target) {
            // Search in left half
            return binarySearch(arr, target, left, mid - 1);
        } else {
            // Search in right half
            return binarySearch(arr, target, mid + 1, right);
        }
    }
    
    public static int search(int[] arr, int target) {
        return binarySearch(arr, target, 0, arr.length - 1);
    }
    
    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15, 17};
        int target = 7;
        
        int result = search(sortedArray, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array");
        }
    }
}

Towers of Hanoi

public class TowersOfHanoi {
    public static void solveTowers(int n, char source, char auxiliary, char destination) {
        // Base case: only one disk to move
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        
        // Recursive case 1: Move n-1 disks from source to auxiliary using destination as auxiliary
        solveTowers(n - 1, source, destination, auxiliary);
        
        // Move the largest disk from source to destination
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        
        // Recursive case 2: Move n-1 disks from auxiliary to destination using source as auxiliary
        solveTowers(n - 1, auxiliary, source, destination);
    }
    
    public static void main(String[] args) {
        int n = 3; // Number of disks
        solveTowers(n, 'A', 'B', 'C');
        /*
         * Output:
         * Move disk 1 from A to C
         * Move disk 2 from A to B
         * Move disk 1 from C to B
         * Move disk 3 from A to C
         * Move disk 1 from B to A
         * Move disk 2 from B to C
         * Move disk 1 from A to C
         */
    }
}