Module 10: Recursion Flashcards
10.1 Recursion
What is recursion?
๐ Recursion is an iterative process where a method calls itself
- Breaking problems into similar sub-problems of the same form
- Problems get so small they are easy to solve
10.1 Recursion
What is a base case?
๐ Process gets to the point where it canโt be simplified anymore, this is the Base Case
- Ex: sum(0)=0
- All of our other numbers can be represented generically with a formula such as the one below:
sum(n) = n + sum(n - 1)
10.1 Recursion
Problem:
Given an Array/ArrayList, return the sum of all the values from the beginning to the target index
public int sumArray(int[] nums, int index){
if(index < 0) {
return 0;
}
return nums[index] + sumArray(nums, index - 1);
}
public static void main(String[] args) {
int[] myNums = {1, 2, 3, 4, 5};
System.out.println(sumArray(myNums, myNums.length-1));
}
10.1 Recursion
Question: 1
What is the definition of recursion?
- Recursion is when we break problems down into smaller parts.
- Recursion is when we have multiple methods in our hierarchy
- Recursion is when a method calls itself.
- Recursion is when a method from a superclass overrides a method from the subclass.
- Recursion is when a method calls itself
10.1 Recursion
Question: 2
What is the base case is a recursive statement?
- The base case is the simplest problem to solve.
- The base case is the line where the function returns a value.
- The base case is the line where the recursive call is made.
- The base case is the call from the original program that starts the recursive process.
- The base case is the simplest problem to solve
10.1 Recursion
Question: 3
Why do we use recursion?
- We use it to break complex problems down into simpler problems that become easier to solve.
- Recursion can be used in place of a loop.
- Neither of these options.
- Both of these options
- Both of these options
10.1 Recursion
Question: 4
Of the following problems, which one would a recursive function work best with?
- A program that asks a user for a Celsius temperature and returns a Fahrenheit temperature.
- Creating a choose your own adventure game using branching logic.
- Calculating factorial.
Recall: 5 factorial = 5 * 4 * 3 * 2 * 1 - All of these options work well
- Calculating factorial.
Recall: 5 factorial = 5 * 4 * 3 * 2 * 1
10.1 Recursion
Question: 5
Given the following code, how many calls (including the original call) to theprintX method would be made if we called with printX(20, 15); ?
public static void printX(int x, int y) {
System.out.print(x + โ โ);
if (x > y) {
printX(x - 1, y);
}
}
1
3
6
10
6
10.2 Recursive Searching
What are the two common recursive practices?
(1) Searches
(2) Sorts
10.2 Recursive Searching
What is linear search?
Linear Searches:
Checks each element in order until the desired value or the end of the array is reached
- Start of the first elements and check value
- Continue until target found
- Exit loop and report results
10.2 Recursive Searching
What is the linear search algorithm?
- Start of the first elements and check value
- Continue until target found
- Exit loop and report results
10.2 Recursive Searching
What is binary search?
Binary Searches:
Find the midpoint of an array and check if the value is greater than or less than the target. Then eliminates half the values and repeats the process.
An array must be sorted for a binary search
- Test midpoint
- Eliminate half of the population
- Find the midpoint of the remainder
- Repeat until target found
10.2 Recursive Searching
What is binary search efficiency and how is it calculated?
Maximum number of iterations needed for a binary search is roughly calculated using a logarithmic function:
log2arraySize
Or think about it in powers of 2.
Given x iterations, you can search 2x times
Ex: Given array of 512, what is the maximum number of iterations will it take to find an item?
log2 512 = 9
10.2 Recursive Searching
What is the algorithm for iteration for binary search code?
10.2 Recursive Searching
What is the algorithm for recursive for binary search code?
10.2 Recursive Searching
What is the difference between iteration and recursive for binary search code?
- For binary search, either approach offers roughly the same efficiency
- Choose based on personal preference