Unit 4c: Recursion
Sources
Adapted from: 1) Building Java Programs: A Back to Basics Approach by Stuart Reges and Marty Stepp
Runestone CSAwesome Curriculum
Recursion
Definition:
- Recursion is defined as the definition of an operation in terms of itself, which means solving a problem using recursion requires solving smaller occurrences of the same problem.Recursive Programming:
- Writing methods that call themselves to solve problems recursively. This serves as a powerful substitute for iteration (loops) and is particularly effective for certain types of problems.
Problems with Recursion
Common Issues:
- Recursion may introduce complexities such as stack overflow errors if not managed properly, particularly if the base case is not reached, leading to infinite recursion.
Why Learn Recursion?
Cultural Experience:
- It provides a different paradigm for thinking about problems.Efficiency:
- Recursion can solve some problems more effectively compared to iteration.Elegance:
- Leads to concise and elegant code when applied correctly.Exclusive use in Functional Languages:
- Languages such as Scheme, ML, and Haskell often rely solely on recursion instead of loops.
Recursion and Cases
Every Recursive Algorithm Contains Two Fundamental Cases:
- Base Case:
- A simple instance that can be answered directly.
- Recursive Case:
- A more complex instance of the problem that cannot be directly solved but can be expressed in terms of smaller instances of the same problem.
- Some recursive algorithms may have multiple base or recursive cases, but at least one of each is essential.
- Identifying these cases is crucial to recursive programming.
Metaphor of Recursion
The metaphor of reducing size is depicted as:
- “I’m not simply repeating myself; I get smaller and smaller… while expending… till I’m as small as needed!”
Example of Recursion
Scenario:
- You are lined up for Black Friday deals, and cannot see the front of the line. To figure out your position, you ask the person in front of you. - Base Case:
- The first person in line will return 1 if asked about their position.
- Recursive Case:
- If a person at position n is asked, they will ask the person in front of them for their position, thereby reducing the problem size from n to n-1, until reaching the front.
Recursion in Java
Basic Example: Print a line of * characters recursively.
public static void printStars(int n) {
for (int i = 0; i < n; i++) {
System.out.print("*");
}
System.out.println(); // Ends the line of output
}
Write a recursive version (without loops):
public static void printStars(int n) {
if (n == 0) {
System.out.println(); // Base case; ends output
} else {
System.out.print("*");
printStars(n - 1); // Recursive call
}
}
Recursion Zen
Definition of Recursion Zen:
- The art of properly identifying the best set of cases for a recursive algorithm and expressing them elegantly.
Exercises on Recursion
Calculate power: Write a method
powthat takes an integer base and exponent and returns the base raised to that exponent.
public static int pow(int base, int exponent) {
if (exponent == 0) {
return 1; // Base case: any number to 0th power is 1
} else {
return base * pow(base, exponent - 1); // Recursive case
}
}
Recursive Traces
Example Method:
public static int mystery(int n) {
if (n < 10) {
return n;
} else {
int a = n / 10;
int b = n % 10;
return mystery(a + b);
}
}
```
- **Call:** `mystery(648)`
- Result propagated to `return 9:` The breakdown is as follows:
- Starting with a = 64 and b = 8, calls `mystery(72)`, which eventually resolves down to `mystery(9)` = 9.
2. **Another Example Method:**
java public static int mystery(int n){
if (n == 1 || n == 2)
return 2 * n;
else
return mystery(n - 1) - mystery(n - 2);
} `` - **Call:**mystery(4)` - Diagram Analysis: This will have a more complex visual representation, best observed in the lecture animation.
Yet Another Example Method:
public static int mystery(int n) {
if (n < 10) {
return (10 * n) + n;
} else {
int a = mystery(n / 10);
int b = mystery(n % 10);
return (100 * a) + b;
}
}
```
- **Call:** `mystery(348)`
- **Final Result:** This will concatenate results to return `334488`, shown in a detailed diagram in the lecture.
## Recursive Binary Search
- **Implementation Example:**
java public static int bSearch(int[] arr, int left, int right, int x) {
if (right >= left) {
int mid = (left + right) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return bSearch(arr, left, mid - 1, x);
} else {
return bSearch(arr, mid + 1, right, x);
}
}
return -1;
}
- **Use Case:** This method appears frequently on exams and illustrates the effectiveness of recursion in searching algorithms.
## Merge Sort
- **Definition:**
- Merge sort is an algorithm that repeatedly divides data in half, sorts each half, and combines the sorted halves into a sorted whole.
- **Implementation Steps:**
- **Step 1:** Divide the list into two roughly equal halves.
- **Step 2:** Sort the left half.
- **Step 3:** Sort the right half.
- **Step 4:** Merge the two sorted halves into one sorted list.
- This algorithm is often implemented recursively and is an example of a "divide and conquer" strategy notable for its efficiency.
- **Historical Note:** Invented by John von Neumann in 1945.
## Merge Sort Example
- **Initial Array:**
> index 0 1 2 3 4 5 6 7
> value 22 18 12 -4 58 7 31 42
- **Execution Flow:**
- The process involves recursive splitting, sorting, and merging, ultimately resulting in a sorted array.
- Visualization aids such as animations enhance understanding of the merge process, highlighting detailed steps of sorting operations.
## Merge Sort Code
- **Merging Method:**
java public static void merge(int[] result, int[] left, int[] right) {
int i1 = 0; // Index for left array
int i2 = 0; // Index for right array
for (int i = 0; i < result.length; i++) { if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
result[i] = left[i1]; // Take from left
i1++;
} else {
result[i] = right[i2]; // Take from right
i2++;
}
}
}
- **General Merge Sort Algorithm:**
java public static void mergeSort(int[] a) {
if (a.length >= 2) {
int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
mergeSort(left);
mergeSort(right);
merge(a, left, right);
}
} ```
Complexity of Sorting Algorithms
Selection Sort
Time Complexity Class (Big-Oh):
-O(n^2)Runtime Data:
- Sample data provided shows increasing runtime with input size N.
Merge Sort
Time Complexity Class (Big-Oh):
-O(n ext{log} n)Runtime Data:
- Sample runtime data indicates significantly lower time compared to selection sort as N increases, highlighting the efficiency of merge sort for larger datasets.
Conclusion
Recursion offers an essential approach to problem-solving in programming, with an array of applications ranging from sorting algorithms to practical scenarios in data manipulation. Understanding both its advantages and challenges is vital for any aspiring programmer.