Module 10: Recursion

Question 1

10.1 Recursion

What is recursion?

Answer 1

📌 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

Question 2

10.1 Recursion

What is a base case?

Answer 2

📌 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)

Question 3

10.1 Recursion

Problem:

Given an Array/ArrayList, return the sum of all the values from the beginning to the target index

Answer 3

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));

}

Question 4

10.1 Recursion

Question: 1

What is the definition of recursion?

1. Recursion is when we break problems down into smaller parts.
2. Recursion is when we have multiple methods in our hierarchy
3. Recursion is when a method calls itself.
4. Recursion is when a method from a superclass overrides a method from the subclass.

Answer 4

3. Recursion is when a method calls itself

Question 5

10.1 Recursion

Question: 2

What is the base case is a recursive statement?

1. The base case is the simplest problem to solve.
2. The base case is the line where the function returns a value.
3. The base case is the line where the recursive call is made.
4. The base case is the call from the original program that starts the recursive process.

Answer 5

1. The base case is the simplest problem to solve

Question 6

10.1 Recursion

Question: 3

Why do we use recursion?

1. We use it to break complex problems down into simpler problems that become easier to solve.
2. Recursion can be used in place of a loop.
3. Neither of these options.
4. Both of these options

Answer 6

4. Both of these options

Question 7

10.1 Recursion

Question: 4

Of the following problems, which one would a recursive function work best with?

1. A program that asks a user for a Celsius temperature and returns a Fahrenheit temperature.
2. Creating a choose your own adventure game using branching logic.
3. Calculating factorial.
   Recall: 5 factorial = 5 * 4 * 3 * 2 * 1
4. All of these options work well

Answer 7

3. Calculating factorial.
   Recall: 5 factorial = 5 * 4 * 3 * 2 * 1

Question 8

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

Answer 8

6

Question 9

10.2 Recursive Searching

What are the two common recursive practices?

Answer 9

(1) Searches
(2) Sorts

Question 10

10.2 Recursive Searching

What is linear search?

Answer 10

Linear Searches:
Checks each element in order until the desired value or the end of the array is reached

1. Start of the first elements and check value
2. Continue until target found
3. Exit loop and report results

Question 11

10.2 Recursive Searching

What is the linear search algorithm?

Answer 11

1. Start of the first elements and check value
2. Continue until target found
3. Exit loop and report results

Question 12

10.2 Recursive Searching

What is binary search?

Answer 12

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

1. Test midpoint
2. Eliminate half of the population
3. Find the midpoint of the remainder
4. Repeat until target found

Question 13

10.2 Recursive Searching

What is binary search efficiency and how is it calculated?

Answer 13

Maximum number of iterations needed for a binary search is roughly calculated using a logarithmic function:

log₂arraySize

Or think about it in powers of 2.
Given x iterations, you can search 2^x times

Ex: Given array of 512, what is the maximum number of iterations will it take to find an item?

log₂ 512 = 9

Question 14

10.2 Recursive Searching

What is the algorithm for iteration for binary search code?

Answer 14

Question 15

10.2 Recursive Searching

What is the algorithm for recursive for binary search code?

Answer 15

Question 16

10.2 Recursive Searching

What is the difference between iteration and recursive for binary search code?

Answer 16

• For binary search, either approach offers roughly the same efficiency
• Choose based on personal preference

Question 17

10.2 Recursive Searching

What is the difference between Linear Search and Binary Search?

Answer 17

Linear Searches: Iteration only eliminated 1 item from our search

Binary Searches: Each iteration eliminates roughly half of our remaining population

Question 18

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

Answer 18

8

Question 19

10.2 Recursive Searching

Question: 2

What is the precondition for binary search to work on an array?

1. The array must be sorted.
2. The array must contain only integers.
3. The array must be of even size.
4. The array must be of odd size.
5. The element being searched for must be in the array.

Answer 19

1. The array must be sorted

Question 20

10.2 Recursive Searching

Question: 3

For a large dataset (roughly 100,000 items), which search is more efficient to find a value?

1. Linear searches are significantly more efficient.
2. Linear searches are slightly more efficient.
3. Both will perform about the same.
4. Binary searches are slightly more efficient.
5. Binary searches are significantly more efficient.

Answer 20

5. Binary searches are significantly more efficient

Question 21

10.2 Recursive Searching

Question: 4

Which best describes how a binary search works?

1. Binary searches start at the beginning and check each item as it walk through the list
2. 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.
3. Binary searches start in the middle and eliminate half of the list in each iteration until the desired value is found.
4. Binary searches split the list in half and creates a dual process to check each half of the list at the same time.

Answer 21

3. Binary searches start in the middle and eliminate half of the list in each iteration until the desired value is found

Question 22

10.2 Recursive Searching

Question: 5

A binary search can be written either with a loop or with a recursive function.

(True or False)

Answer 22

True

Question 23

10.3 Recursive Sorting

How can you sort data sets for the use of binary search?

Answer 23

1. Insertion Sort (Unit 07)
2. Selection Sort (Unit 07)
3. Merge Sort (Unit 10)

Question 24

10.3 Recursive Sorting

What is merge sort?

Answer 24

🤖 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

Question 25

# Module 10 Recursion Quiz **Question: 1** Which best describes a merge sort algorithm? 1. Merge sort is a recursive sorting algorithm that can be used to sort elements. 2. Merge sort is a linear sorting algorithm that can be used to sort elements in an array or ArrayList. 3. Merge sort is a binary sorting algorithm that can be used to sort elements in an array or ArrayList. 4. Merge sort is a random sorting algorithm that can be used to sort elements in an array or ArrayList.

Answer 25

1. Merge sort is a recursive sorting algorithm that can be used to sort elements

Question 26

# Module 10 Recursion Quiz **Question: 2** How does a merge sort work? 1. Sorts an array by repeatedly finding the minimum value, and moving it to the front of the array 2. Sorts an array by sorting each element compared to the elements already sorted to their left. 3. Sorts an array by dividing a list into parts, then merging it back together in the correct order. 4. Sorts an array by repeatedly swapping the adjacent elements if they are in wrong order

Answer 26

3. Sorts an array by dividing a list into parts, then merging it back together in the correct order

Question 27

# Module 10 Recursion Quiz **Question: 3** Which part of the merge sort is accomplished with recursion? 1. Recursion is used to break the list down repeatedly until it gets to one element. 2. Recursion is used to find the correct order of each element. 3. Recursion is used to put the elements back together once they are broken apart. 4. Recursion is used to determine if the list needs to be sorted.

Answer 27

1. Recursion is used to break the list down repeatedly until it gets to one element

Question 28

# Module 10 Recursion Quiz **Question: 4** What type of data set works best for merge sorts? 1. Randomly sorted lists 2. Nearly sorted lists 3. Reverse sorted lists 4. Neither of these. Merge sorts work the same on all lists.

Answer 28

4.Neither of these. Merge sorts work the same on all lists

Question 29

# Module 10 Recursion Quiz **Question: 5** Why do we use merge sorts? 1. The code is simple and easy to write. 2. They are very efficient regardless of how the data is organized. 3. They are more efficient than other algorithms when it comes to nearly sorted arrays. 4. Merge sorts may look complex, but they don’t take much memory.

Answer 29

2. They are very efficient regardless of how the data is organized

Question 30

# 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

Answer 30

3

Question 31

# 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

Answer 31

14

Question 32

# 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? 1. key is the last element in the array 2. key is in the middle of the array 3. n is very large 4. key is the first element in the array 5. key does not exist in the array

Answer 32

4. key is the first element in the array

Question 33

# Module 10 Recursion Quiz **Question: 4** ## Footnote What is the largest number of comparisons needed to perform a binary search on an array with 42 elements? 2 5 6 41 42

Answer 33

6

Question 34

# Module 10 Recursion Quiz **Question: 5** What approach does MergeSort use? 1. divide and conquer 2. iterative 3. search and swap 4. search and insert

Answer 34

1. divide and conquer

Question 35

# Module 10 Recursion Quiz **Question: 6** Which sorting method is implemented below? 1. Selection sort 2. Insertion sort 3. Mergesort 4. Binary search 5. Sequential search / Linear search

Answer 35

3. Mergesort

Question 36

# 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

Answer 36

III and IV

Question 37

# 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

Answer 37

(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

Question 38

# Module 10 Recursion Quiz **Question: 9** ## Footnote 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.

Answer 38

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.

Question 39

# Module 10 Recursion Quiz Question: 10 ## Footnote Consider the following recursive function: What will be printed if **printDigits(12345)** is called?

Answer 39

5 4 3 2 1

Question 40

# 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? 1. Line 3 should be changed to be \> 0 instead of \< 0 2. Line 5 should be return 1 instead of return 0 3. Line 7 should just return the recursive call, not add 1. 4. Line 5 should be changed to return 1 and line 7 should be changed to just return the recursive call, not add 1. 5. The first parameter of the recursive call should be phrase.substring(phrase.indexOf(word)+ 1)

Answer 40

5. The first parameter of the recursive call should be phrase.substring(phrase.indexOf(word)+ 1)

Question 41

# 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

Answer 41

5

Question 42

# 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

Answer 42

7