Below is a series of problems divided into several categories. We expect students from CS111 to be able to complete all the core problems. There are challenge problems within the core problems that are harder and more like problem set questions. You may not be able to complete them in class but given enough time we would expect you to implement them. There are also some challenging problems like sublistSum at the end to give you more practice with "choose-it-or-lose-it" recursion.
Table of Contents
Core Problems
1.1 Tracing
1.1.1 Mystery function 1
1.1.2 Mystery function 2
1.1.3 Mystery function 3
1.1.4 Challenge: Mystery function 4
1.2 Writing non-fruitful recursive functions
1.2.1 Subtract four
1.2.2 Count up by four
1.2.3 Carrot border
1.2.4 Challenge: Hourglass word
1.3 Writing fruitful recursive functions
1.3.1 Power
1.3.2 Sum of squares
1.3.3 Count vowels
1.3.4 List of end strings
1.3.5 Challenge: Is it a palindrome?Challenging "Choose-it-or-lose-it" Problems
2.1 Longest Common Subsequence
2.2 String PermutationsTracing is an important skill for understanding computer programs and especially for recursive code. In the following problems, predict the printed output of the functions before running the code. Confirm your answers afterwards.
def mystery(x):
if x < 1:
print("Your last number is:", x)
elif x % 2 == 0:
print("Even number:", x)
mystery(x + 1)
else:
print("Odd number:", x)
mystery(x - 3)
mystery(0)
mystery(1)
mystery(5)
mystery(8)
In the function below, the keyword argument end="" is specifying the string appended after the last value, because the default is a newline. That is, if we don't want the values to show each on a new line, we specify a character like the empty string instead.
def mystery2(x, y):
if y == 1:
print(x, end="")
else:
print(f"{x * y}, ", end="")
mystery2(x, y - 1)
print(f", {x * y}", end="")
mystery2(4, 5)
mystery2(2, 3)
mystery2(0, 5)
def mystery3(s):
if s == "":
return ""
else:
return mystery3(s[1:]) + s[0]
mystery3("bat")
mystery3("mystery")
mystery3("testing")
mystery3("ADA")
Question: What slicing operation has the same behavior as mystery3?
Note that this one is a bit harder and is more of a challenge problem.
def mystery4(s):
if s == "":
return 0
elif s[0] == "1":
return 2 ** (len(s) - 1) + mystery4(s[1:])
else:
return mystery4(s[1:])
mystery4("1001")
mystery4("10000")
mystery4("1")
Question: Can you figure out what mystery4 is computing?
"CS" + str(mystery4("11110000")) # Take this class to learn more :-)
Write a recursive function similar to countDown (that we saw in lecture) that counts down from a multiple of 4 down to zero by the number 4. You can assume the input is a non-negative multiple of four. Here is an example:
subtractFour(16)
16
12
8
4
0def subtractFour(num):
# Your code here
if num >= 0:
print(num)
subtractFour(num - 4)
subtractFour(4)
subtractFour(16)
subtractFour(144)
Write a recursive function called countUpByFour that takes a number n and counts up from 0 by four up to and including n * 4. For example:
countUpByFour(3)
0
4
8
12def countUpByFour(num):
# Your code here
if num >= 0:
countUpByFour(num - 1)
print(num * 4)
countUpByFour(3)
countUpByFour(10)
countUpByFour(1)
countUpByFour(0)
Write a recursive function carrotBorder that has two parameters s and num and puts num instances of ">" on the left side of a word and num instances of "<" on the right side of word. The result should be printed. For example, the call of carrotBorder("INCEPTION", 4) should print >>>>INCEPTION<<<<.
def carrotBorder(s, num):
# Your code here
if num == 0:
print(s, end="")
else:
print(">", end="")
carrotBorder(s, num - 1)
print("<", end="")
carrotBorder("INCEPTION", 4)
carrotBorder("AWESOME", 9)
carrotBorder("COOL", 3)
carrotBorder("", 20)
Note that this problem is more challenging. In this problem, you will make an hourglass shape using asterisks as borders around a particular word. hourglassWord takes three parameters: a word, the currentRow and the number of rows. You'll need both the currentRow and the total number of rows as you recurse to ensure that you create the proper spacing/padding for each row. Here's a sample of the output for hourglassWord("MINDBLOWING", 5, 5):
*****MINDBLOWING*****
****MINDBLOWING****
***MINDBLOWING***
**MINDBLOWING**
*MINDBLOWING*
MINDBLOWING
*MINDBLOWING*
**MINDBLOWING**
***MINDBLOWING***
****MINDBLOWING****
*****MINDBLOWING*****def hourglassWord(s, currentRow, numRows):
# Your code here
padding = (numRows - currentRow) * ' '
if currentRow == 0:
print(padding + s + padding)
else:
stars = "*" * currentRow
print(padding + stars + s + stars + padding)
hourglassWord(s, currentRow - 1, numRows)
print(padding + stars + s + stars + padding)
hourglassWord("MINDBLOWING", 5, 5)
hourglassWord("WHOA", 10, 10)
hourglassWord("A", 1, 1)
hourglassWord("SAND", 30, 30)
Write a function that computes the power of a number recursively. This problem is very similar to the factorial problem. One way to think about x to the power of n is as x * x ^ (n - 1). Write the function toPowerOf which computes x to the power of n. Assume x and n are both non-negative.
def toPowerOf(x, n):
# Your code here
if n == 0:
return 1
else:
return x * toPowerOf(x, n - 1)
toPowerOf(3, 4) # should return 81
toPowerOf(5, 7) # should return 78125
toPowerOf(0, 3) # should return 0
Write a function called sumOfSquares that takes a non-negative number n and sums up all the values of 0^2 + 1^2 + 2^2 + 3^2 + ... n^2.
def sumOfSquares(n):
# Your code here
if n == 0:
return 0
else:
return n ** 2 + sumOfSquares(n - 1)
sumOfSquares(0) # Should return 0
sumOfSquares(2) # Should return 5
sumOfSquares(5) # Should return 55
sumOfSquares(85) # Should return 208335
We have seen the iterative version of this problem. Let's try and solve this using recursion. Given the function isVowel below, write a function countVowels that takes a word and returns a count of the number of vowels in the word.
def isVowel(letter):
return letter.lower() in "aeiou"
def countVowels(word):
# Your code here
if word == "":
return 0
elif isVowel(word[0]):
return 1 + countVowels(word[1:])
else:
return countVowels(word[1:])
countVowels("beauteous") # should return 6
countVowels("precarious") # should return 5
countVowels("") # should return 0
countVowels("gfh") # should return 0
Write a function called listOfEndStrings that accumulates a list of the different endings for a given string. For example, listOfEndStrings("abcde") should return the list ["e", "de", "cde", "bcde", "abcde"] and listOfEndStrings("Andy") should return the list ["y", "dy", "ndy", "Andy"].
def listOfEndStrings(s):
# Your code here
if s == "":
return []
else:
return listOfEndStrings(s[1:]) + [s]
listOfEndStrings("abcde")
listOfEndStrings("Andy")
listOfEndStrings("y")
Write a function called isPalindrome that takes a string and returns True if the string is a palindrome and False otherwise. Remember that a palindrome is a word or phrase that reads the same forwards of backwards like "racecar". This is a little trickier because we have not examined fruitful recursive functions that return booleans.
def isPalindrome(word):
# Your code here
if word == "":
return True
elif word[0] != word[-1]:
return False
else:
return isPalindrome(word[1:-1])
isPalindrome("racecar") # should return True
isPalindrome("tenet") # should return True
isPalindrome("Andy") # should return False
isPalindrome("abcdba") # should return False
These are more like problem set questions. These problems are hard and similar to sublistSum. But, if you completed all the core problems, you are welcome to try these out.
In this problem, you will determine the longest common subsequence between two words. A subsequence is like a substring except the letters need not be consecutive. Order still matters though. For example, the longest common subsequence between "smart" and "ant" is "at". The longest common subsequence between "tile" and "lite" is "ie". Note that the order of the letters still matters which is why the "t" and "l" are not included in the longest common subsequence of "tile" and "lite". If the two words have multiple longest common subsequence, you need only return one.
Note that the recursive implementation of LCS is inefficient. It's actually faster to calculate the LCS using a technique called dynamic programming which you can learn more about in CS231.
def longestCommonSubsequence(word1, word2):
# Your code here
if word1 == "" or word2 == "":
return ""
elif word1[0] == word2[0]:
return word1[0] + longestCommonSubsequence(word1[1:], word2[1:])
else:
seq1 = longestCommonSubsequence(word1[1:], word2)
seq2 = longestCommonSubsequence(word1, word2[1:])
if len(seq1) > len(seq2):
return seq1
else:
return seq2
longestCommonSubsequence("rat", "at") # should return "at"
longestCommonSubsequence("asp", "ap") # should return "ap"
longestCommonSubsequence("art", "") # should return ""
longestCommonSubsequence("locomotion", "elocution") # should return "loction"
longestCommonSubsequence("grandiose", "splendor") # should return "ndo"
longestCommonSubsequence("", "") # should return ""
Write a function called stringPermutations that prints out all the string permutations of a given word. Let's assume that the word has distinct characters. For example, all the permutations of "ABC" are as follows:
"ABC"
"ACB"
"BAC"
"BCA"
"CBA"
"CAB"To solve this problem you cannot recurse using just stringPermutations, you need to create a helper function to perform the recursion. Think about what extra arguments you might need in this helper function in order to solve the problem recursively.
def stringPermutations(word):
# Your code here
stringPermutationsHelper(word, 0)
def stringPermutationsHelper(word, index):
if index == len(word):
print(word)
else:
# Keep the letter
stringPermutationsHelper(word, index + 1)
# Swap the current letter at index with all the later letters
wordBeforeIndex = word[:index]
letterToSwap = word[index]
for i in range(index + 1, len(word)):
newWord = wordBeforeIndex + word[i] + word[index + 1:i] + letterToSwap + word[i + 1:]
stringPermutationsHelper(newWord, index + 1)
stringPermutations("ABC")
stringPermutations("Andy")