Unit 10 Lesson
Java Recursion
Learning Targets:
- Determine the result of executing recursive method.
Essential Knowledge:
- Recursion is a method that calls itself.
- Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.
- To accomplish this is a recursive method contains a conditional.
- each recursive call has its own set of local variables, including formal parameters.
- parameter values capture the progress of a recursive process, much like a loop control variable vales capture the progress of a loop.
- any recursive sloution can be replicated throu the user of an i word (iteration, index, or integer) approach.
- exclusion statement: writing recursive program code is outside the scope of the AP CSA course and exam but it is allowed. but sometimes it is more straightforward than iterative.
### Example of recursion:### Example of recursion with a base case:
public static void main(String[] args) { System.out.println("Hello World!"); main(args); }
### Example of recursion with a base case and a recursive call including formal parameters:public static void main(String[] args) { System.out.println("Hello World!"); if (args.length > 0) { main(args); } }
public static void main(String[] args) { System.out.println("Hello World!"); if (args.length > 0) { main(args); } }
- exclusion statement: writing recursive program code is outside the scope of the AP CSA course and exam but it is allowed. but sometimes it is more straightforward than iterative.
### Example of recursion:
This is a recursive code, do we all agree with that?
note : pay attention
// void recursive method
public static void simpleRecur(int n)
{
system.out.println(n);
if (n > 2) // the if statement cuases the recursion to end when n <. 2 since the recursive call
// since the recursive call only occurs when n > 2
simpleRecur(n-1);
system.out.println(n);
}
lets trace the call simpleRecur(4) | Call Stack | Variable trace for call | |---|---| | simpleRecur(4) | n=4 4>2, T | | simpleRecur(3) | n=3 2>2, T | | simpleRecur(2) | n=2 2>2, F |
pop corn hack!!!!!!
Note: 0.01 extra credit for each correct answer, we have limit Paraas to 3 answers.
What would be the output of the code above? (0.01 extra credit)
4
3
3
4
here is a modified code from above, what would be the output of the code above? and what would be the base case? (0.01 extra credit)
4
7
10
13
16
and so on...continues to increase indefinitely
// infinite
public static void simpleRecur(int n)
{
system.out.println(n);
if (n > 2)
simpleRecur(n+3);
system.out.println(n);
}
Call Stack | Variable trace for call |
---|---|
simpleRecur(4) | n=4 4>2, T |
simpleRecur(7) | n=7 7>2, T |
simpleRecur(10) | n=10 10>2, T |
n is getting larger infinitely. java will eventually run out of memory and cause a CallStackOverflowException
.
// non-void recursive method
public static void simpleRecur(int n)
{
system.out.println(n);
if (n == 0)
return 0;
return n + system.out.println(n);
}
Call Stack | Variable trace for call |
---|---|
simpleRecur(8)=8 + simpleRecur(4) | n=8 8==0 F |
simpleRecur(4)=4 + simpleRecur(2) | n=4 4==0 F |
simpleRecur(2)=2 + simpleRecur(1) | n=2 2==0 F |
simpleRecur(1)=1 + simpleRecur(0) | n=1 1==0 F |
simpleRecur(0)=0 | n= 0==0 T |
but where does it return 0 to?
Enter the password to answer:
what would be the return of simpleRecur(8)?
Enter the password answer:
most of this might have flew over your head, but don't fret.
real world examples of recursion:
Russian dolls
- Russian dolls are a set of wooden dolls of decreasing size placed one inside another.
- The dolls are made in such a way that each doll can be opened in half to reveal a smaller doll inside.
- Lets set the smallest as the base case
- The dolls are a recursive structure because each doll is a smaller version of the previous doll.
mr. finn here is gonna talk about how to visualize recursion better.
//iterative approach to binary search
// This is a method for performing a binary search on a sorted integer array.
// It returns the index of the target element if found, or -1 if the element is not in the array.
public static int binarySearch(int[] intArray, int lowPosition, int highPosition, int target) {
int midPosition;
// Use a while loop to repeatedly divide the search range in half.
while (lowPosition <= highPosition) {
// Calculate the middle position of the current search range.
midPosition = (highPosition + lowPosition) / 2;
// If the element at the middle position is less than the target,
// we narrow our search to the right half of the current range.
if (intArray[midPosition] < target) {
lowPosition = midPosition + 1;
}
// If the element at the middle position is greater than the target,
// we narrow our search to the left half of the current range.
else if (intArray[midPosition] > target) {
highPosition = midPosition - 1;
}
// If the element at the middle position is equal to the target,
// we have found our target, and we return its index.
else {
return midPosition;
}
}
// If the while loop completes without finding the target, we return -1 to indicate it's not in the array.
return -1;
}
public static int recBinarySearch(int[] intArray, int lowPosition, int highPosition, int target) {
int midPosition;
// Check if the lower index is greater than the higher index, indicating an empty search range.
if (lowPosition > highPosition) {
// If the low index is greater than the high index, the target element is not found.
return -1;
} else {
// Calculate the middle index of the current search range.
midPosition = (lowPosition + highPosition) / 2;
// If the element at the middle index is less than the target, search in the right half of the array.
if (intArray[midPosition] < target) {
// Recursively call the function with an updated search range (right half).
return recBinarySearch(intArray, midPosition + 1, highPosition, target);
}
// If the element at the middle index is greater than the target, search in the left half of the array.
if (intArray[midPosition] > target) {
// Recursively call the function with an updated search range (left half).
return recBinarySearch(intArray, lowPosition, midPosition - 1, target);
}
// If the element at the middle index is equal to the target, we found the target element.
// Return the index where the target element is found (midPosition).
return midPosition;
}
}
tracing through a runthrough
int Array: |0|2|4|6|8|10|12|14|16|18|20|22| Target: 12
recBinarySearch(intArray, 0, 10, 12);
Call 1: Midpoint calculated as (0 + 10) / 2 = 5 The target value 12 is greater than the midpoint value at index 5 (10). So, we narrow our search to values greater than the midpoint.
Call 2: recBinarySearch(intArray, mid1, high, target) Midpoint 1 calculated as (mid + high) / 2 = 7
The midpoint value at index 7 is 14, which is greater than 12, so the next call is between low and mid.
Call 3: Another recursive call finds the midpoint value at index 6, as it's between low and mid, which is our target number.
If the target does not exist, we would print -1 as the value is not found.
public static int recBinarySearch(int[] intArray, int lowPosition, int highPosition, int target) {
int midPosition;
// Check if the lower index is greater than the higher index, indicating an empty search range.
if (lowPosition > highPosition) {
// If the low index is greater than the high index, the target element is not found.
return -1;
} else {
// Calculate the middle index of the current search range.
midPosition = (lowPosition + highPosition) / 2;
// If the element at the middle index is less than the target, search in the right half of the array.
if (intArray[midPosition] < target) {
// Recursively call the function with an updated search range (right half).
return recBinarySearch(intArray, midPosition + 1, highPosition, target);
}
// If the element at the middle index is greater than the target, search in the left half of the array.
if (intArray[midPosition] > target) {
// Recursively call the function with an updated search range (left half).
return recBinarySearch(intArray, lowPosition, midPosition - 1, target);
}
// If the element at the middle index is equal to the target, we found the target element.
// Return the index where the target element is found (midPosition).
return midPosition;
}
}
int[] intArray = {9, 4, 7, 2, 5, 8, 1, 3, 6};
// Sort the array in ascending order.
Arrays.sort(intArray);
// Call the binary search function on the sorted array.
int target = 5; // Replace with the target value you want to search for.
int result = recBinarySearch(intArray, 0, intArray.length - 1, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index " + result);
}
takeaways
Data must be in sorted order for binary search to work.
The binary search algorithm starts in the middle of the sorted array or arraylist and and eliminates half of the array or arraylist in each iteration until the desired value is found or all elements have been eliminated
Binary search can be more effective than linear search
binary search algorithm can be written linearly or recursively
mergeSort(myList) {
mergeSort(left)
mergeSort(right)
}
// left, right merge
example trace (look at the whiteboard, I will draw it out maybe)
Original List: |5|25|8|-9|14|0|-2|2|
The first recursive call begins by splitting the list into the left and right sides: (5, 25, 8, -9).
Another recursive call is made on the left side, which further splits into (5, 25).
The left and right sides are split into individual elements, and the two elements (5 and 25) are merged, resulting in (5, 25).
The current list becomes (5, 25, -9, 8).
The current list is sorted, resulting in (-9, 5, 8, 25).
Current List:
|-9|5|8|25|14|0|-2|2|
The final left side is sorted, and a recursive call is made for the right side: (14, 0, -2, 2).
The right side is further split into (14, 0).
These two elements (14 and 0) are merged into (0, 14).
The remaining elements (-2 and 2) are merged into (-2, 2).
The right side is now (0, 14, -2, 2).
Current List: |-9|5|8|25|0|14|-2|2|
The left and right sides are finally merged together:
Left: -9, 5, 8, 25
Right: 0, 14, -2, 2
The two merged sides are sorted, resulting in the final sorted list: |-9|0|2|5|8|14|25|
The merge sort process is complete, and the original list is sorted: Sorted List: |-9|0|2|5|8|14|25|
Merge Method ---The **merge** method
// work from left to right in each virtual myArray
// compare elements to return them to the original array in order
int[] myArray = {3, 4, 6, 8, 1, 2, 5, 7}
// think of the temporary array as two virtual arrays
int[] myArray1 = {3, 4, 6, 8};
int[] myArray2 = {1, 2, 5, 7};
// have to throw an exception for the last one to end the code
// if any elements remain in the lower half of the temporary array, return them to the original array
- 1 < 3, 1 goes to the first place
- 2 < 3, 2 goes to the second place
- 3 < 5, 3 goes to the third place
4. 4 < 5, 4 goes to the fourth place
5. 5 < 6, 5 goes to the fifth place
6. 6 < 7, 6 goes to the sixth place
7. 7 < 8, 7 goes tot the seventh place
8. 8 goes to the last place
public class sort {
public static int[] output;
public static void __mergeSort(int[] myArray, int left, int right) {
if(left < right) {
int i;
int center = (left + right) / 2;
int p = 0;
int j = 0;
int k = left;
__mergeSort(myArray, left, center); // sort front part
__mergeSort(myArray, center + 1, right); // sort back part
for(i = left; i <= center; i++) {
output[p++] = myArray[i];
}
// comparing the elements and put in myArray
while (i <= right && j < p) {
if (output[j] <= myArray[i]) {
myArray[k] = output[j];
j++;
} else {
myArray[k] = myArray[i];
i++;
}
k++;
}
// put the remain in myArray
while (j < p) {
myArray[k++] = output[j++];
}
}
}
public static void mergeSort(int[] myArray) {
output = new int[myArray.length];
__mergeSort(myArray, 0, myArray.length - 1);
output = null;
}
public static void printArray(int[] array) {
for(int data: array) {
System.out.print(data + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {3, 4, 6, 8, 1, 2, 5, 9};
System.out.println("before");
printArray(array);
mergeSort(array);
System.out.println("after");
printArray(array);
}
}
sort.main(null);
hack
Question: what are the usage cases of merge sort? what about usage cases of recursive binary sort? try and come up with a real life scenario for each usage case.
- Merge Sort is good for sorting large datasets, especially in scenarios where stability and parallel processing are required. For example, it can efficiently sort product listings in commerce platforms.
- Recursive Binary Search is suitable for searching in large, sorted datasets, making it ideal for applications like finding a specific book in a library catalog organized by title.
%maven org.knowm.xchart:xchart:3.5.2
import org.knowm.xchart.*;
public class Example0 {
public static void main(String[] args) throws Exception {
// these vars hold your X and Y values
double[] xData = new double[] { 0.0, 1.0, 2.0 };
double[] yData = new double[] { 2.0, 1.0, 0.0 };
// Create Chart
XYChart chart = QuickChart.getChart("Sample Chart", "X", "Y", "y(x)", xData, yData);
// Show it
new SwingWrapper(chart).displayChart();
}
}
Example0.main(null);
private static void graph(double[] xData, double[] yData, int index, double x, int maxIndex, double stepSize) {
if (index > maxIndex) {
return;
}
xData[index] = x;
yData[index] = x * x;
graph(xData, yData, index + 1, x + stepSize, maxIndex, stepSize);
}
%maven org.knowm.xchart:xchart:3.5.2
import org.knowm.xchart.*;
public class recursiveGraph {
public static void main(String[] args) throws Exception {
int numPoints = 100;
double[] xData = new double[numPoints];
double[] yData = new double[numPoints];
plotParabola(xData, yData, 0, -5.0, numPoints - 1, 0.1);
// Create Chart
XYChart chart = QuickChart.getChart("Parabola", "X", "Y", "y(x)", xData, yData);
// Show it
new SwingWrapper(chart).displayChart();
}
private static void plotParabola(double[] xData, double[] yData, int index, double x, int maxIndex, double stepSize) {
if (index > maxIndex) {
return;
}
xData[index] = x;
yData[index] = x * x;
plotParabola(xData, yData, index + 1, x + stepSize, maxIndex, stepSize);
}
}
RecursiveGraph.main(null);
private static void plot(double[] xData, double[] yData, int index, double x, int maxIndex, double stepSize, double base) {
if (index > maxIndex) {
return;
}
xData[index] = x;
yData[index] = Math.pow(base, x);
plot(xData, yData, index + 1, x + stepSize, maxIndex, stepSize, base);
}
%maven org.knowm.xchart:xchart:3.5.2
import org.knowm.xchart.*;
public class recursiveGraph2 {
public static void main(String[] args) throws Exception {
int numPoints = 100;
double[] xData = new double[numPoints];
double[] yData = new double[numPoints];
plotExponential(xData, yData, 0, -5.0, numPoints - 1, 0.1, 2.0); // You can adjust the base as needed (e.g., 2.0 for 2^x)
// Create Chart
XYChart chart = QuickChart.getChart("Mati Yapping Graph", "Seconds of Mati Yapping", "My Anger", "y(x)", xData, yData);
// Show it
new SwingWrapper(chart).displayChart();
}
private static void plotExponential(double[] xData, double[] yDawta, int index, double x, int maxIndex, double stepSize, double base) {
if (index > maxIndex) {
return;
}
xData[index] = x;
yData[index] = Math.pow(base, x);
plotExponential(xData, yData, index + 1, x + stepSize, maxIndex, stepSize, base);
}
}
recursiveGraph2.main(null);
Hacks
- Finish all popcorn hacks for the lesson
- Follow the directions bellow for the XChart Hacks
Example of Cool Function for the Hacks
- If you are having trouble with thinking of a cool equation to put into a recursion form, follow these tips
- Look up the shape/symbol you would like to put into the graph
- Try to split the equation up into what math methods you will need
- Ask the friend who know most about coding (wink wink)
- Make sure to take a screenshot of the graph and display it next to it's respective code block
%maven org.knowm.xchart:xchart:3.5.2
import org.knowm.xchart.*;
public class HeartShapeGraph {
public static void main(String[] args) throws Exception {
int numPoints = 100;
double[] xData = new double[numPoints];
double[] yData = new double[numPoints];
plotHeartShape(xData, yData, 0, 0, numPoints - 1);
// Create Chart
XYChart chart = QuickChart.getChart("Heart Shape", "X", "Y", "y(x)", xData, yData);
// Show it
new SwingWrapper(chart).displayChart();
}
private static void plotHeartShape(double[] xData, double[] yData, int index, double t, int maxIndex) {
if (index > maxIndex) {
return;
}
//Chat GPT Math
xData[index] = 16 * Math.pow(Math.sin(t), 3);
yData[index] = 13 * Math.cos(t) - 5 * Math.cos(2 * t) - 2 * Math.cos(3 * t) - Math.cos(4 * t);
plotHeartShape(xData, yData, index + 1, t + (2 * Math.PI) / maxIndex, maxIndex);
}
}
HeartShapeGraph.main(null);
%maven org.knowm.xchart:xchart:3.5.2
import org.knowm.xchart.*;
public class FlowerShapeGraph {
public static void main(String[] args) throws Exception {
int numPoints = 360; // Increase for a smoother flower
double[] xData = new double[numPoints];
double[] yData = new double[numPoints];
plotFlowerShape(xData, yData, 0, 0, numPoints - 1);
// Create Chart
XYChart chart = new XYChartBuilder().width(800).height(600).title("Flower Shape").xAxisTitle("X").yAxisTitle("Y").build();
chart.addSeries("Flower Shape", xData, yData);
// Show it
new SwingWrapper(chart).displayChart();
}
private static void plotFlowerShape(double[] xData, double[] yData, int index, double t, int maxIndex) {
if (index > maxIndex) {
return;
}
double r = 50; // Adjust the radius as needed
double k = 5; // Adjust the number of points on the flower
double x = r * Math.cos(t) * Math.cos(k * t);
double y = r * Math.sin(t) * Math.cos(k * t);
xData[index] = x;
yData[index] = y;
plotFlowerShape(xData, yData, index + 1, t + (2 * Math.PI) / maxIndex, maxIndex);
}
}
FlowerShapeGraph.main(null)