| Summing together:
|
4 + simpleRecur3(2) + simpleRecur3(1) + simpleRecur3(0)
4 + 2 + 1 + 0 = 7
</td>
</tr>
</table>
Knowing how to trace a recursion and its inner workings is one of the skills required for AP exams.
### Popcorn Hack 1 - Factorial
Introduction
Factorials are a common technique which may be easy to implement using recursion. This is due to their repetitive nature in terms of multiplication. Please complete the factorial method below. The comments in the code may help you out a bit.
```python
// 5! = 5 * 4! = 5 * (5 – 1)!
// 4! = 4 * 3! = 4 * (4 – 1)!
// ...
// 1! = 1
public static int factorial(int target) {
// your code here
}
```
### Skill 5.A (10.1.2)
Review from 10.1.1
* A recursive method is a method which calls itself
Anatomy of a Recursive Method (CON-2.0.2)
* A recursive method must have at least one base case and at least one recursive call
* What is a base case? A base case is a condition which breaks the recursive function
* It is ABSOLUTELY important to have a base case or else this happens
* [Recursion Moment](https://www.youtube.com/watch?v=3K3MMtoG8rY)
* 
* Having two calls is also acceptable
Method Refresher (CON-2.0.3)
* Like every other method, recursive methods have their local variables and parameters. Local variables can be helpful when constructing a base method to exit out of the recursive method. Formal parameters are also needed.
* A local variable is only accessible to the inside of a function
*
Parameters Capture the Progress of the Recursive Function (CON-2.0.4)
* Every parameter in a recursive system is sort of like a capture. It gives us the information we need to determine the next element in a sort of series of captures.
* This stems from the definition of a method or function with its inputs and outputs.
* Example: I want to make a program to reverse a string in Java. I can write down each call and slowly once the calls reach an end, I can start tracking the print statements BACKWARDS
Recursion and Iteration (CON-2.0.5)
* Every iterative approach has a recursive solution
* Recursion is just another way of looping. In assembly, loops work through instructions such as `jmp `which in easy terms, jump to another line of code. This is how loops work. Just constant jumping.
* There is another instruction called `ret `and another called `ret `which basically also jumps to other parts of the program. Because they are so similar to`jmp`, they can be used to solve the same problems.
### Popcorn Hack 2 - Recurse Through an Arrays
Introduction
Using your knowledge of local and global variables, create a recursive method which recurses through an array instead of iterating through it
```python
// Pro tip: Think of why the index is stored as a parameter
// What are parameters usually used as?
public static int sumArray(int[] arr, int index) {
// your code here
}
```
## 10.2) Recursive Searching and Sorting
### Skill 2.D (10.2.1) - Binary Search
Learning Objective
* CON-2.P
* Apply recursive search algorithms to information in `String`, 1D array, or `ArrayList` objects.
Essential Knowledge
* CON-2.P.1
* Data must be sorted in sequential order so you can use binary search
* CON-2.P.2
* The binary search algorithm starts at the middle of a sorted array (or `ArrayList`) and eliminates half of the array (or `ArrayList`) in each iteration until the desired value is found or all elements have been eliminated.
* CON-2.P.3
* Binary search can be more efficient than sequential/linear search.
* **Important**: any search algorithms apart from linear and binary search will not be tested on the AP Exam and are out of the scope for AP CSA.
* CON-2.P.4
* The binary search algorithm can be written iteratively or recursively.
**Binary search w/recursion:**
* Draft a binary search algorithm with recursion (**cannot use loops**)
* What do we do if `lowPosition` is greater than `highPosition`?
* What do we do if the middle value is less than `target`?
* What do we do if the middle value is greater than `target`?
* What do we do if the middle value is equal to `target`?
* Show code:
* `intArray = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40]`
* Call 1: `binarySearchRecursive(intArray, 0, 20, 24)`
* `midPosition = (0 + 20) / 2 = 10`
* `intArray[midPosition] = intArray[10] = 20`
* `intArray[midPosition] < 24 (intArray[midPosition] < target)`
* Our middle value (20) was less than the target (24), so we can eliminate the bottom half of the list. We call the function again but this time, we only look at the top half (we set the lower bounds to the middlePosition + 1)
* Call 2: `binarySearchRecursive(intArray, 11, 20, 24)`
* Now, we only look at the values [`24, 26, 28, 30, 32, 34, 36, 38, 40]`.
* `midPosition = (11 + 20) / 2 = 15`
* `intArray[midPosition] = intArray[15] = 30`
* `intArray[midPosition] > 30 (intArray[midPosition] > target)`
* The new middle value of 30 is greater than 24, so we can eliminate the top half of the list. When we call the function again, we only change the upper bound to ignore values greater than or equal to 30.
* Call 3: `binarySearchRecursive(intArray, 11, 14, 24)`
* Now, we only look at the values [`24, 26, 28]`.
* `midPosition = (11 + 14) / 2 = 12`
* `intArray[midPosition] = intArray[12] = 24`
* `intArray[midPosition] = target`
* We found that the target value of 24 is located in the 12th position. We return the midPosition (12) as the final answer.
### Popcorn Hack 3 - Selection sort
Introduction
Using your knowledge of local variables, global variables, and parameters, please create a recursive method which sorts an array through selection.
```python
// Pro tip: Set max to the first element
public static int sumArray(int[] arr, int index, int max) {
// your code here
}
```
### Skill 2.C (10.2.2) - Merge Sort 😍
Learning Objective
* CON-2.Q
* Apply recursive algorithms to sort elements of array or `ArrayList` objects.
Essential Knowledge
* CON-2.Q.1
* Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or `ArrayList`.
**How it works:**
|
When you merge sort, you recursively call the sorting function. You first look at the left half of the list, then the right half, and then both. Remember: left, right, merge; left, right, merge…
|
|
We first call the mergeSort() function on the entire list. Remember, we look at the left half first.
On the first call (at the bottom of the “tree”), the algorithm takes the left half of the list. It keeps going until there are no more halves left (it reached the end of the branch).
</td>
</tr>
|
</td>
| When it reached the end of the branch (5), it would consider that call to be complete. It goes back and then considers the right branch (25). Again, it reached the end.
So to summarize what we did: if the array is the tree, we went to go find the end of the branches on the left side. In our case, we found the ends to be 5 and 25. When we remerge, we will sort them. So in this case, 5 < 25 so that branch is already sorted.
</td>
</tr>
|
</td>
| We do the same thing but with the other branch. However, the numbers are out of order this time. When we merge the 8 branch and the -9 branch, we flip the numbers.
|
</tr>
|
Now, we are back at the larger branch of the four numbers. When we merge, we are going to sort the numbers again.
|
|
The numbers are sorted. You’ll see that on the parent branch (at the very bottom), the left half of the array is fully sorted. This whole process is repeated on the right half of the array. Eventually, the whole array will be sorted.
|
</table>
### Skill 2.C (10.2.3) - Merge Sort: The Actual Code
|
Variable to keep track of the left most value of the parent array
Variables to keep track of the left most value of the child arrays (the left and right halves)
</td>
</tr>
|
|
We compare the value at index 0 and index 4. Since 1 < 3, we replace the value at index 0 of the parent array with 1.
|
</td>
| Increment the variable in the parent array and the 2nd half (child array).
Compare the values and then update the parent array.
</td>
</tr>
|
</td>
| Everything done above is done again. Increment the variables, compare, and update.
However, this time, 3 < 5. Basically, a value from the left child array is less than the value from the right child array (the previous two iterations were the opposite). So, when we update the parent array, we will put 3 to replace 6. Then, we increment the variable for the left child array.
</td>
</tr>
|
|
What happens when we reach the end? Here, you can see that the arrow is outside the array so we will get an out of bounds error. In this case, we would need to have a clause in the code that just tells us to copy over the 8 to the final element in the array.
|
</table>
### Popcorn Hack 4 - 2D Array Recursion
Introduction
Using your knowledge of local variables, global variables, and parameters, please create a recursive method which sorts an array through selection. Remember you have your parameters to keep your indices, just keep track of your indices.
```python
// Pro tip: Remember what we learned from the 1D Array Popcorn Hack
public static int sumArray(int[][] arr, int x_index, int y_index) {
}
```
### Homework Hack 1 - APEL Teacher Collaboration
Introduction
The APEL teachers at Del Norte a, b, and c as much as the Calculus teachers love x, y, and z. Make a program which prints out each letter in the alphabet which has a position which is a multiple of 3. If the number is not a multiple of 3, print (“X”).
```python
// Pro tip: The thread of calls will likely not turn out to be too violent.
public static int sumArray(int[] arr, int index) {
// your code here
}
```
### Homework Hack 2 - Recruiting Scrum Slaves for Mr. Mortensen!!!
Introduction
Mr. Mortensen needs help recruiting new Scrum Slaves to help integrate his project. However, he has a dilemna on who to recruit for this job!
Luckily for you, you have three statistics for each student:
* collab - How well they collaborate with fellow students!
* iq - The intelligence level of the student (who wouldn’t want someone smart?)
* efficiency - The efficiency at which they work at (time is of the essence to Mr. Mortensen!)
Using these three statistics, please calculate a performance score for each student, and sort them into an array (using an algo of your choice!) in descending order.
Here are the list of students with their statistics:
| Student
|
collab
|
iq
|
efficiency
|
| srijus
|
98
|
95
|
92
|
| aadit
|
95
|
97
|
97
|
| erox
|
90
|
93
|
89
|
| shubs
|
92
|
94
|
90
|
| aashray
|
50
|
53
|
59
|
```python
// Pro tip: Think of why the index is stored as a parameter
// What are parameters usually used as?
public class Student {
String name;
int efficiency, collab, iq;
int performanceScore;
public Student (String name, int efficiency, int collab, int iq) {
this.name = name;
this.efficiency = efficiency;
this.collab = collab;
this.iq = iq;
this.performanceScore = calculatePerformanceScore();
}
public int calculatePerformanceScore() {
return (collab * 2) + (iq * 3) + efficiency;
}
}
public static int sumArray(int[] arr, int index) {
// your code here
}
```
|