Unit 7: Recursion and Sorting Algorithms
Recursion
- Recursion: A programming technique where a method calls itself to solve a problem.
- Base Case: A condition that terminates the recursion.
int factorial(int n) { if (n == 0) { return 1; // Base case } else { return n * factorial(n - 1); // Recursive call }
- Recursive Call: A call to the same method within itself to make progress toward the base case.
int sum(int[] arr, int index) { if (index == arr.length) { return 0; // Base case } else { return arr[index] + sum(arr, index + 1); // Recursive call }
Sorting Algorithms
- Selection Sort: A simple sorting algorithm that repeatedly selects the minimum element from the unsorted portion and moves it to the beginning.
void selectionSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }
- Quick Sort: A fast, divide-and-conquer sorting algorithm that partitions the array into smaller segments.
void quickSort(int[] arr, int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } int partition(int[] arr, int low, int high) { // Choose a pivot and rearrange the elements around it // Return the final position of the pivot }
Unit 8: Object-Oriented Programming and Design
Abstraction
- Abstraction: Focusing on essential features while hiding unnecessary details.
- Abstract Classes: Classes marked as abstract that cannot be instantiated, used for creating a common base for other classes.
abstract class Shape { abstract double area(); }
- Abstract Methods: Methods declared in abstract classes that have no implementation and must be overridden in subclasses.
class Circle extends Shape { double radius; @Override double area() { return Math.PI * radius * radius; }
Static Members
- Static Variables: Variables shared among all instances of a class. Accessed with the class name.
class MathUtils { static final double PI = 3.14159265359;
- Static Methods: Methods that belong to the class, not the instance. Accessed with the class name.
static int add(int a, int b) { return a + b; }