AP Computer Science A Unit 10 Review

AP Computer Science A Unit 10 Review with Java Code

1. Recursion

Recursion is a programming technique where a method calls itself to solve a problem. It involves breaking down a problem into smaller subproblems, solving each subproblem recursively, and combining the results to obtain the final solution.

public class RecursionExample {
    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println("Factorial of 5: " + result);
    }
    
    // Recursive method to calculate factorial
    static int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

2. Recursive Searching and Sorting

Recursion can be used in searching and sorting algorithms, such as binary search and merge sort.

• Binary Search: A recursive algorithm that searches for a target value in a sorted array by repeatedly dividing the search interval in half.

// Recursive binary search
static int binarySearch(int[] arr, int low, int high, int target) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid; // Element found
        } else if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, high, target); // Search in the right half
        } else {
            return binarySearch(arr, low, mid - 1, target); // Search in the left half
        }
    }
    return -1; // Element not found
}

Merge Sort: A recursive sorting algorithm that divides the array into two halves, recursively sorts each half, and then merges the sorted halves.

// Recursive merge sort
static void mergeSort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        mergeSort(arr, low, mid); // Sort left half
        mergeSort(arr, mid + 1, high); // Sort right half
        merge(arr, low, mid, high); // Merge sorted halves
    }
}