recursion

Question 1

recursive functions often use more system resources than their iterative counterparts

Answer 1

true

Question 2

recursion might make the program “easier” for other programmers to read at the cost of system resources (e.g. stack usage)

Answer 2

true

Question 3

following a list of non-repeating /known instructions (driving directions) is best suited to …

Answer 3

use iteration to go through a list of instructions

Question 4

trying to find a store in a city (unknown directions, need to look at all possibilities)… is best suited to…

Answer 4

use recursion for maze-solving/ backtracking type searches. Break into smaller problems (does this street contain the store?) and either recurse or backtrack from there

Question 5

binary search keeps track of lower bound, upper bound, middle value: if middle value is higher than search value…

Answer 5

means search item is in lower half of array
1. discard upper half of array
2. (middle index + 1) becomes upper bound
3. lower index stays same
redo recursive search with middle index = (UB-LB)/2

Question 6

binary search keeps track of lower bound, upper bound, middle value: if middle value is lower than search value…

Answer 6

means search item is in upper half of array
1. discard lower half of array
2. (middle index -1) becomes lower bound
3. upper index stays same
redo recursive search with middle index = (UB-LB)/2

Question 7

what is a magic index

Answer 7

an index of a list that has the same value as the index m[i]=i