Module 10: Recursion Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

10.1 Recursion

What is recursion?

A

๐Ÿ“Œ 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

10.1 Recursion

What is a base case?

A

๐Ÿ“Œ 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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

10.1 Recursion

Problem:

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

A

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

}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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.
A
  1. Recursion is when a method calls itself
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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.
A
  1. The base case is the simplest problem to solve
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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
A
  1. Both of these options
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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
A
  1. Calculating factorial.
    Recall: 5 factorial = 5 * 4 * 3 * 2 * 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

6

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

10.2 Recursive Searching

What are the two common recursive practices?

A

(1) Searches
(2) Sorts

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

10.2 Recursive Searching

What is linear search?

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

10.2 Recursive Searching

What is the linear search algorithm?

A
  1. Start of the first elements and check value
  2. Continue until target found
  3. Exit loop and report results
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

10.2 Recursive Searching

What is binary search?

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

10.2 Recursive Searching

What is binary search efficiency and how is it calculated?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

10.2 Recursive Searching

What is the algorithm for iteration for binary search code?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

10.2 Recursive Searching

What is the algorithm for recursive for binary search code?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

10.2 Recursive Searching

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

A
  • For binary search, either approach offers roughly the same efficiency
  • Choose based on personal preference
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

10.2 Recursive Searching

What is the difference between Linear Search and Binary Search?

A

Linear Searches: Iteration only eliminated 1 item from our search

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

18
Q

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

A

8

19
Q

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.
A
  1. The array must be sorted
20
Q

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.
A
  1. Binary searches are significantly more efficient
21
Q

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.
A
  1. Binary searches start in the middle and eliminate half of the list in each iteration until the desired value is found
22
Q

10.2 Recursive Searching

Question: 5

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

(True or False)

A

True

23
Q

10.3 Recursive Sorting

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

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

10.3 Recursive Sorting

What is merge sort?

A

๐Ÿค– 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
25
Q

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.
A
  1. Merge sort is a recursive sorting algorithm that can be used to sort elements
26
Q

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
A
  1. Sorts an array by dividing a list into parts, then merging it back together in the correct order
27
Q

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.
A
  1. Recursion is used to break the list down repeatedly until it gets to one element
28
Q

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.
A

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

29
Q

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.
A
  1. They are very efficient regardless of how the data is organized
30
Q

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

A

3

31
Q

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

A

14

32
Q

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
A
  1. key is the first element in the array
33
Q

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

A

6

34
Q

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
A
  1. divide and conquer
35
Q

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
A
  1. Mergesort
36
Q

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

A

III and IV

37
Q

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

A

(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

38
Q

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.

A

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.

39
Q

Module 10 Recursion Quiz

Question: 10

Consider the following recursive function:

What will be printed if printDigits(12345) is called?

A

5

4

3

2

1

40
Q

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)
A
  1. The first parameter of the recursive call should be phrase.substring(phrase.indexOf(word)+ 1)
41
Q

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

A

5

42
Q

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

A

7