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
10.2 Recursive Searching
What is the difference between Linear Search and Binary Search?
Linear Searches: Iteration only eliminated 1 item from our search
Binary Searches: Each iteration eliminates roughly half of our remaining population
10.2 Recursive Searching
Question: 1
Using the binary search algorithm, what is the maximum number of iterations needed to find an element in an array containing 256 elements?
128
256
4
8
16
8
10.2 Recursive Searching
Question: 2
What is the precondition for binary search to work on an array?
- The array must be sorted.
- The array must contain only integers.
- The array must be of even size.
- The array must be of odd size.
- The element being searched for must be in the array.
- The array must be sorted
10.2 Recursive Searching
Question: 3
For a large dataset (roughly 100,000 items), which search is more efficient to find a value?
- Linear searches are significantly more efficient.
- Linear searches are slightly more efficient.
- Both will perform about the same.
- Binary searches are slightly more efficient.
- Binary searches are significantly more efficient.
- Binary searches are significantly more efficient
10.2 Recursive Searching
Question: 4
Which best describes how a binary search works?
- Binary searches start at the beginning and check each item as it walk through the list
- Binary searches start at the beginning and check every other item until it finds a value greater than the search, then goes back if needed.
- Binary searches start in the middle and eliminate half of the list in each iteration until the desired value is found.
- Binary searches split the list in half and creates a dual process to check each half of the list at the same time.
- Binary searches start in the middle and eliminate half of the list in each iteration until the desired value is found
10.2 Recursive Searching
Question: 5
A binary search can be written either with a loop or with a recursive function.
(True or False)
True
10.3 Recursive Sorting
How can you sort data sets for the use of binary search?
- Insertion Sort (Unit 07)
- Selection Sort (Unit 07)
- Merge Sort (Unit 10)
10.3 Recursive Sorting
What is merge sort?
🤖 Merge Sort work by dividing a list into parts, then merging it back together in the correct order
- Repeatedly divide a list in half until the list is only one element long, then merge these one item lists back together
- A recursive sorting algorithm for both arrays and ArrayLists
- Relatively efficient, but the algorithm is somewhat complex
Module 10 Recursion Quiz
Question: 1
Which best describes a merge sort algorithm?
- Merge sort is a recursive sorting algorithm that can be used to sort elements.
- Merge sort is a linear sorting algorithm that can be used to sort elements in an array or ArrayList.
- Merge sort is a binary sorting algorithm that can be used to sort elements in an array or ArrayList.
- Merge sort is a random sorting algorithm that can be used to sort elements in an array or ArrayList.
- Merge sort is a recursive sorting algorithm that can be used to sort elements
Module 10 Recursion Quiz
Question: 2
How does a merge sort work?
- Sorts an array by repeatedly finding the minimum value, and moving it to the front of the array
- Sorts an array by sorting each element compared to the elements already sorted to their left.
- Sorts an array by dividing a list into parts, then merging it back together in the correct order.
- Sorts an array by repeatedly swapping the adjacent elements if they are in wrong order
- Sorts an array by dividing a list into parts, then merging it back together in the correct order
Module 10 Recursion Quiz
Question: 3
Which part of the merge sort is accomplished with recursion?
- Recursion is used to break the list down repeatedly until it gets to one element.
- Recursion is used to find the correct order of each element.
- Recursion is used to put the elements back together once they are broken apart.
- Recursion is used to determine if the list needs to be sorted.
- Recursion is used to break the list down repeatedly until it gets to one element
Module 10 Recursion Quiz
Question: 4
What type of data set works best for merge sorts?
- Randomly sorted lists
- Nearly sorted lists
- Reverse sorted lists
- Neither of these. Merge sorts work the same on all lists.
4.Neither of these. Merge sorts work the same on all lists
Module 10 Recursion Quiz
Question: 5
Why do we use merge sorts?
- The code is simple and easy to write.
- They are very efficient regardless of how the data is organized.
- They are more efficient than other algorithms when it comes to nearly sorted arrays.
- Merge sorts may look complex, but they don’t take much memory.
- They are very efficient regardless of how the data is organized
Module 10 Recursion Quiz
Question: 1
Given this array:
1 2 4 5 6 7 8 12 14 21 22 42 53
How many comparisons are required to find 42 using the Binary Search?
3
2
10
5
3
Module 10 Recursion Quiz
Question: 2
BMO the robot is programming a new game called “Open the box!” You give him a number and he tries to open a numbered box. He’s using Binary Search to accomplish this. Unfortunately, the boxes are not sorted. They are in the following order:
1 3 6 9 14 10 21
Which box can NEVER be found using binary search?
9
6
14
10
14
Module 10 Recursion Quiz
Question: 3
We are searching for an int key in a sorted int array that has n elements. Under what circumstances will Linear Search / Sequential Search be more efficient than Binary Search?
- key is the last element in the array
- key is in the middle of the array
- n is very large
- key is the first element in the array
- key does not exist in the array
- key is the first element in the array
Module 10 Recursion Quiz
Question: 4
What is the largest number of comparisons needed to perform a binary search on an array with 42 elements?
2
5
6
41
42
6
Module 10 Recursion Quiz
Question: 5
What approach does MergeSort use?
- divide and conquer
- iterative
- search and swap
- search and insert
- divide and conquer
Module 10 Recursion Quiz
Question: 6
Which sorting method is implemented below?
- Selection sort
- Insertion sort
- Mergesort
- Binary search
- Sequential search / Linear search
- Mergesort
Module 10 Recursion Quiz
Question: 7
How are Selection Sort and Insertion Sort different?
I – Selection Sort is always faster than Insertion Sort
II – Insertion Sort is always faster than Selection Sort
III – When Selection Sort places an element into the sorted part of the array, that element is in its final position, whereas Insertion Sort may move the element later if it finds a smaller element. Selection Sort builds up an absolutely sorted array as it goes while Insertion Sort builds up a relatively sorted array as it goes.
IV – Insertion Sort is faster if the array is already sorted or close to sorted
I only
II only
II and IV
II and III
III and IV
III and IV
Module 10 Recursion Quiz
Question: 8
What is the correct pseudocode for Insertion Sort?
(1) If there are at least two elements in the collection
Partition the collection
Insertion sort the left collection
Insertion sort the right collection
(2) If there is more than one element in the collection
Break the collection into two halves
Insertion sort the left half
Insertion sort the right half
Compare the two halves
Merge the two subcollections into a sorted collection
(3) For each element in the collection
While there is a next element
Compare the next unsorted element with the sorted elements
Insert the element into the correct position in the sorted elements
(4) While there are unsorted numbers
Find the smallest unsorted number
Insert the element at the end of the sorted elements
(3) For each element in the collection
While there is a next element
Compare the next unsorted element with the sorted elements
Insert the element into the correct position in the sorted elements
Module 10 Recursion Quiz
Question: 9
Consider the following recursive function:
How many times will the function mystery be called if we call mystery(5) (be sure to include the first call mystery(5))
5
6
4
10
The recursion will go on forever because there is no base case.
6
Correct! There will be 6 calls. mystery(5), mystery(4), mystery(3), mystery(2), mystery(1), and mystery(0). n == 0 is the base case.
Module 10 Recursion Quiz
Question: 10
Consider the following recursive function:
What will be printed if printDigits(12345) is called?
5
4
3
2
1
Module 10 Recursion Quiz
Question: 11
The following recursive method is intended to return the number of occurrences of a word from a phrase.
Which of the following best describes why this method does not work as intended?
- Line 3 should be changed to be > 0 instead of < 0
- Line 5 should be return 1 instead of return 0
- Line 7 should just return the recursive call, not add 1.
- Line 5 should be changed to return 1 and line 7 should be changed to just return the recursive call, not add 1.
- The first parameter of the recursive call should be phrase.substring(phrase.indexOf(word)+ 1)
- The first parameter of the recursive call should be phrase.substring(phrase.indexOf(word)+ 1)
Module 10 Recursion Quiz
Question: 13
Including the initial call, how many times will the sumDigits method be called if the initial call is sumDigits(4734)?
1
3
4
5
5
Module 10 Recursion Quiz
Question: 15
The following recursive method is designed to adjust letter grades for students receiving a B, C, or D.
Including the original call, how many times will the method be called using the following line of code:
adjustGrades(“AACDBA”);
3
4
7
8
7
