USING PYTHON: Write a recursive function makeChange(amount, coinVal1, coinVal2,
ID: 3796319 • Letter: U
Question
USING PYTHON: Write a recursive function makeChange(amount, coinVal1, coinVal2, coinVal3) that determines whether or not change for amount (where amount is an integer), can be made using coins (any number of them) of the three given integer values. If the answer is yes, the function should return a list of a coin values totalling amount. Otherwise, return False.
For example:
No loops are needed nor allowed. Use only if statements, recursion, and simple math operations.
Heres what I got so far:
#QUESTION 2
def makeChange(amount, coinVal1, coinVal2, coinVal3):
# Stopping condition for failure
if amount < 0:
return False
# Stopping condtion for success
elif amount == 0:
return [ ]
# Needs to keep going else:
#need to check three cases
r1 = makeChange(amount - coinVal1, coinVal1, coinVal2, coinVal3)
if r1 != False:
#return something
r1.append(coinVal1)
# do something with result
r2 = makeChange(amount - coinVal2, coinVal1, coinVal2, coinVal3)
if r2 != False:
# do something with result
r1.append(coinVal2)
r3 = makeChange(amount - coinVal3, coinVal1, coinVal2, coinVal3)
if r3 != False:
r1.append(coinVal3)
Explanation / Answer
def makeChange(a1,a2,a3,a4):
if a1<0:
return False
if(a1 is 0):
return []
b1 = makeChange(a1-a2,a2,a3,a4)
if b1 != False :
return [a2]+b1
b2 = makeChange(a1-a3,a2,a3,a4)
if b2 != False :
return [a3]+b2
b3 = makeChange(a1-a4,a2,a3,a4)
if b3 != False:
return [a4]+b3
return False
d = makeChange(64,5,11,13)
print(d)
d = makeChange(7,3,5,12)
print(d)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.