unit 5 - recursion

Question 1

recursion

Answer 1

when a function calls itself

Question 2

recursion is useful when

Answer 2

something calls for a repeated process with different values / close values, but only returning one value

Question 3

iterative > recursion for

Answer 3

speed and memory

Question 4

Recursive > iterative for

Answer 4

keeping track of previous steps

Question 5

branching path problems

Answer 5

different conditions require different procedures;
recursion is useful for finding the optimal path

Question 6

Abstract data type best representing recursive function calls

Answer 6

stack

Question 7

greedy algorithm

Answer 7

takes the step that brings it closest to its goal at every junction

Question 8

coin counting: greedy algorithm

Answer 8

sort coin values;
for each value, while it is less than the amount of money needed, subtract that value from the amount;
append # of coins for each subtraction operation

Question 9

downside to greedy algorithms

Answer 9

the biggest step is not always the most efficient;
with arbitrary coins, a coin counting algorithm may not take the most efficient steps. Less coins will be received with a different coin

Question 10

coin counting: recursive algorithm

Answer 10

if amt in coins: return 1;
validcoins = [c in coins if c < amt];
for coin in valuelist: numcoins = 1 + fewest_coins(amt - coin, coins);
If numcoins < mincoins: mincoins = numcoins

Question 11

memoization

Answer 11

the practice of storing a subset of solved problems