def sumk(k):
if k > 0:
return sumk(k-1) + k
return 0
print(sumk(1))
print(sumk(2))
print(sumk(3))
print(sumk(4))
print(sumk(5))1
3
6
10
15March 17, 2025
Goals: make wise decisions about correctness and performance when designing, implementing, maintaining, and revising programs
SingleLinkedList and DoubleLinkedList!sumkdef sumk(k):
if k > 0:
return sumk(k-1) + k
return 0
print(sumk(1))
print(sumk(2))
print(sumk(3))
print(sumk(4))
print(sumk(5))1
3
6
10
15sumk function calls itself with a smaller value of kk is equal to 0sumk functionsumk function’s behavior?
RecursionErrorsumsquarek functiondef sumsquarek(k):
if k == 0:
return 0
else:
return k ** 2 + sumsquarek(k - 1)
print(sumsquarek(1)) # Output: 1
print(sumsquarek(2)) # Output: 5
print(sumsquarek(3)) # Output: 14
print(sumsquarek(4)) # Output: 30
print(sumsquarek(5)) # Output: 551
5
14
30
55sumsquarek function calls itself with a smaller value of kk is equal to 0sumsquarek functionsumsquarek function? Why does it crash?
RecursionError with functionsRecursionError in PythonRecursionError!RecursionError in PythonRecursionError with listslist.__eq__ method that compares two lists for == useA and B are equalA and B are actually listslist.__eq__ methodRecursionError in Pythondef fibonacci_recursive(k):
if k in [0,1]: return k
return fibonacci_recursive(k-1) + fibonacci_recursive(k-2)
print([fibonacci_recursive(i) for i in range(10)])[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
def fibonacci_iterative(k):
a, b = 0,1
for i in range(k):
a, b = b, a + b
return a
print([fibonacci_iterative(i) for i in range(10)])[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]fibonacci_recursive and fibonacci_iterativedef gcd(a, b):
if a == b:
return a
if a > b:
a, b = b, a
return gcd(a, b - a)
print("GCD of 12 and 513 is", gcd(12, 513))
print("GCD of 19 and 513 is", gcd(19, 513))
print("GCD of 19 and 515 is", gcd(515, 19))GCD of 12 and 513 is 3
GCD of 19 and 513 is 19
GCD of 19 and 515 is 1b is much larger than a!gcddef gcd_revised(a, b):
if a > b:
a, b = b, a
if a == 0:
return b
return gcd_revised(a, b % a)
print("GCD of 12 and 513 is", gcd_revised(12, 513))
print("GCD of 19 and 513 is", gcd_revised(19, 513))
print("GCD of 19 and 515 is", gcd_revised(515, 19))GCD of 12 and 513 is 3
GCD of 19 and 513 is 19
GCD of 19 and 515 is 1Empirically comparing the performance of iterative and recursive functions
time.perf_counter() for precise measurementtimetrials() that runs multiple trialsdef greedyMC(coinvalueList, change):
coinvalueList.sort()
coinvalueList.reverse()
numcoins = 0
for c in coinvalueList:
numcoins += change // c
change = change % c
return numcoins
print(greedyMC([1, 5, 10, 25], 63)) # Correct answer of 6
print(greedyMC([1, 21, 25], 63)) # Incorrect, should be 3
print(greedyMC([1, 5, 21, 25], 63)) # Incorrect, should be 36
15
763 cents? This greedyMC only works for “canonical” coin systems!def recMC(coinValueList, change):
minCoins = change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recMC(coinValueList,change-i)
if numCoins < minCoins:
minCoins = numCoins
return minCoins
print(recMC([1, 5, 10, 25], 63))
print(recMC([1, 21, 25], 63))
print(recMC([1, 5, 21, 25], 63))recMC calls itself with a smaller value of changedef memoMC(coinValueList, change, knownResults):
minCoins = change
if change in coinValueList:
knownResults[change] = 1
return 1
elif change in knownResults:
return knownResults[change]
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + memoMC(coinValueList, change-i, knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
return minCoins
knownresults = {}
print(f"{memoMC([1, 5, 10, 21, 25], 63, knownresults)} coins needed.", end=" ")
print(f"Wow, computed {len(knownresults)} intermediate results!", end=" ")3 coins needed. Wow, computed 60 intermediate results! def dpMakeChange(coinValueList, change):
1 minCoins = [None]*(change + 1)
2 for cents in range(change+1):
3 minCoins[cents] = cents
4 for c in coinValueList:
if cents >= c:
minCoins[cents] = min(minCoins[cents], minCoins[cents - c] + 1)
5 return minCoins[change]
print(dpMakeChange([1,5,10,21,25], 63))0 to change, compute min number of coins
1 coins are used in solution
dpMakeChange functiondpMakeChange functionWhat is the worst-case time complexity of a change-making algorithm?
greedyMC
recMC
memoMC
dpMakeChange
Both algorithmic strategies can compute correct answer! Compare by experimentally studying runtime and analyzing running time.
def lcs_recursive(X, Y):
if X == "" or Y == "":
return ""
if X[-1] == Y[-1]:
return lcs_recursive(X[:-1], Y[:-1]) + X[-1]
else:
return max([lcs_recursive(X[:-1], Y),
lcs_recursive(X, Y[:-1])], key = len)
lcs_str = lcs_recursive('ABCBDAB', 'BDCAB')
lcs_len = len(lcs_str)
print(f"LCS length is {lcs_len} and LCS contents are {lcs_str}")LCS length is 4 and LCS contents are BCABn binary call treelcs_recursivedef lcs_dynamic(X, Y):
t = {}
for i in range(len(X)+1): t[(i,0)] = ""
for j in range(len(Y)+1): t[(0,j)] = ""
for i, x in enumerate(X):
for j, y in enumerate(Y):
if x == y:
t[(i+1,j+1)] = t[(i, j)] + x
else:
t[(i+1,j+1)] = max([t[(i, j+1)], t[(i+1, j)]], key = len)
return t[(len(X), len(Y))]
lcs_str = lcs_dynamic('ABCBDAB', 'BDCAB')
lcs_len = len(lcs_str)
print(f"LCS length is {lcs_len} and LCS contents are {lcs_str}")LCS length is 4 and LCS contents are BCABlcs_dynamicdef lcs_calculate(X, Y):
m = len(X)
n = len(Y)
L = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i - 1] == Y[j - 1]:
L[i][j] = L[i - 1][j - 1] + 1
else:
L[i][j] = max(L[i - 1][j], L[i][j - 1])
return L[m][n]
lcs_len = lcs_calculate('ABCBDAB', 'BDCAB')
print(f"LCS length is {lcs_len}")LCS length is 4lcs_calculate function is \(O(m \times n)\), but does not return the LCS!lcs_recursive)
lcs_dynamic)
lcs_calculate)
Algorithmology