Recursion Implementation

Recursion requires two essential components to function correctly and avoid infinite loops. First, the termination condition (or base case) must be defined; this is the specific scenario where the method stops calling itself and returns a result. Second, the recursive step defines how the method breaks down the problem and calls itself with modified parameters. It is generally advised to avoid recursion for extremely large input sizes, as deep recursion stacks can lead to memory overflow errors.

Stack and Heap Memory Management

In Java, understanding memory distribution involves distinguishing between value types and reference types.

Value Passing: When a primitive variable (e.g., int) is passed to a method, a copy of the value is created. Reassigning the parameter inside the method only changes the local copy; the original variable in the calling method remains unchanged because they point to different memory locations.

Reference Passing: When an object (such as an array) is passed, the reference to the memory address is copied. Consequently, modifying the internal state of the object (e.g., changing an array element) affects the original object, as both references point to the same data on the heap.

public class ReferenceDemo {
    public static void main(String[] args) {
        int[] dataSequence = new int[]{10, 20, 30, 40, 50};
        modifyFirstElement(dataSequence);
        System.out.println("Value after method call: " + dataSequence[0]);
    }

    public static void modifyFirstElement(int[] items) {
        items[0] = 999;
    }
}

Bubble Sort Algorithm

Bubble sort is a simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted.

public class SortingUtil {
    public void executeBubbleSort(int[] numbers) {
        int len = numbers.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int tempBuffer = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = tempBuffer;
                }
            }
        }
    }
}

Sparse Array Compression

Sparse arrays are used to compress data structures that contain mostly default values (typically zeros). By storing only the non-default values along with their coordinates, memory usage is significantly reduced. The conversion process involves counting non-zero elements, creating a compressed array, and populating it with row, column, and value data.

public class SparseMatrix {
    public static int[][] toSparseArray(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int nonZeroCount = 0;

        // Count non-zero elements
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != 0) {
                    nonZeroCount++;
                }
            }
        }

        // Create sparse array [count + 1][3]
        // Row 0 contains meta info: total rows, total cols, non-zero count
        int[][] sparseArr = new int[nonZeroCount + 1][3];
        sparseArr[0][0] = rows;
        sparseArr[0][1] = cols;
        sparseArr[0][2] = nonZeroCount;

        // Fill the sparse array
        int currentRecord = 1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != 0) {
                    sparseArr[currentRecord][0] = i;
                    sparseArr[currentRecord][1] = j;
                    sparseArr[currentRecord][2] = matrix[i][j];
                    currentRecord++;
                }
            }
        }

        // Output the result
        for (int[] record : sparseArr) {
            System.out.println(record[0] + "\t" + record[1] + "\t" + record[2]);
        }
        
        return sparseArr;
    }
}