5.9 KiB
Lecture for November 27
Recursion
When doing recursion, make sure not to use loops.
Recursion is when a function makes a function call to itself.
It consists of two parts:
- Base Case: This tell it when to stop
- Smaller Caller Case: Helps you get closer to the base case
You can have one or more base cases or caller cases.
To teach recursion, we'll start with a problem that should be written iteratively (with loops) but we'll show how to do it with recursion.
Example: Counting Down
void CountDown(int number) {
while (number > 0) {
System.out.println(number + " ");
number = number - 1;
}
System.out.println("Blast Off")
}
- How does this loop stop? -- Base Case
- How does this loop change each time through? -- Smaller caller case
Base Case: It stops when the number equals 0
// Base Case
if (number == 0) {
System.out.println("Blast Off");
return;
}
Smaller Caller Case: It decreases number by 1
// Smaller Caller Case
System.out.print(number + " ");
countDownRecursive(number - 1);
Put it together...
void countDownRecursive(int number) {
if (number == 0) {
System.out.println("Blast Off");
} else {
System.out.print(number + " ");
countDownRecursive(number - 1);
}
}
Prints 10 9 8 7 6 5 4 3 2 1 Blast Off
Stack Snapshots
Every time you make a recursive call, it keeps track of all the local variables at the current function call and pushes it onto the stack.
That means if you make 10 recursive calls, you'll have 10 slots added onto the stack. If you want to return back to the beginning, you would need to return 10 times.
Order Matters
Whether you do the recursive step first or some other action, it completely changes the output. Look at the following example that's similar to countDownRecursive.
void countUpRecursive(int number) {
if (number == 0) {
System.out.println("Blast Off");
} else {
// Notice the swapping of the next two lines
countUpRecursive(number - 1);
System.out.print(number + " ");
}
}
This would print out Blast Off 1 2 3 4 5 6 7 8 9 10
Example: Summing up to a number
This would be our iterative solution
int sum(int number) {
int sum = 0;
while (number > 0) {
sum += number;
number--;
}
return sum;
}
How does this loop stop?
Same as before. Think about it, if the number you pass in is zero, what should be the result of sum? Zero. Since adding up from 0 to 0 is just 0.
if (number == 0) {
return 0;
}
How does this loop change each time through?
You want to update your sum, so return the sum of the next call to the current sum.
return (number + sum(number - 1));
Putting it all together
int sumRecursive(int number) {
if (number == 0) {
return 0;
} else {
return number + sumRecursive(number - 1);
}
}
Example: Linear Search
How to do it iteratively.
void linearSearch(int[] array, int number) {
int i = 0;
while (i < array.length && number != array[i]) {
i++;
}
if (i == array.length) {
System.out.println("Not Found");
} else {
System.out.println("Found");
}
}
Base Case: There are two base cases, when it reaches the end of the array and when it finds the number
if (array.length == i) {
System.out.println("Not Found");
} else (array[i] == number) {
System.out.println(number + " found at index " + i);
}
Smaller Caller Case: Check the next element
linearSearchRecursion(number, array, i + 1);
Putting it all together...
void linearSearchRecursion(int[] array, int number) {
if (array.length == i) {
System.out.println("Not Found");
} else if (array[i] == number) {
System.out.println(number + " found at index " + index);
} else {
linearSearchRecursion(number, array, i + 1);
}
}
Binary Search
This is a much more efficient search than the linear search we have been doing. The only condition is that your array must be sorted beforehand.
A regular linear search O(n) -- Check at most all of the elements of the array.
Binary Search O(log(n)) -- Checks at most ceil(log(n)) elements of an array.
To demonstrate this with real numbers, let's take an array of 100 elements
- With linear search this will take at most 100 iterations
- With binary search this will take at most 7.
Crazy right?
Implementation
Iterative approach
void binarySearch(int number, int[] array) {
int lower = 0;
int upper = array.length - 1;
int mid = (lower + upper) / 2
while (lower <= upper && array[mid] != number) {
mid = (lower + upper) / 2;
if (array[mid] < number) {
lower = mid + 1;
} else if () {
upper = mid -1;
}
}
if (lower > upper) {
System.out.println("Not Found");
} else {
System.out.println(number + " found at index " + mid);
}
}
Recursive Approach
Base Case: There are two cases, you either found it, or you made it to the end of the array without finding it
if (lower > upper) {
System.out.println("Not Found");
} else if (array[mid] == number) {
System.out.println(number + " found at index " + mid);
}
Smaller Caller Case: Change the lower or upper bounds to cut the search in half
if (array[mid] < number) {
lower = mid + 1;
binarySearchRecursive(number, array, lower, upper);
} else if (array[mid] > number) {
upper = mid - 1;
binarySearchRecursive(number, array, lower, upper);
}
Putting it together....
binarySearch(int number, int[] array, int lower, int upper) {
if (lower > upper) {
System.out.println("Not Found");
} else if (array[mid] == number) {
System.out.println(number + " found at index " + mid);
}
else if (array[mid] < number) {
lower = mid + 1;
binarySearchRecursive(number, array, lower, upper);
} else if (array[mid] > number) {
upper = mid - 1;
binarySearchRecursive(number, array, lower, upper);
}
}