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;
  }