# CS 111 Material: Recursion Practice¶

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.

1.  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.1 Subtract four
1.2.2 Count up by four
1.2.3 Carrot border
1.2.4 Challenge: Hourglass word

 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?
2. Challenging "Choose-it-or-lose-it" Problems

 2.1 Longest Common Subsequence
2.2 String Permutations

## 1. Core Problems¶

### 1.1 Tracing¶

Tracing 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.

#### Mystery Function 1¶

In [1]:
def mystery(x):
if x < 1:
elif x % 2 == 0:
print("Even number:", x)
mystery(x + 1)
else:
print("Odd number:", x)
mystery(x - 3)

In [2]:
mystery(0)

Your last number is: 0

In [3]:
mystery(1)

Odd number: 1

In [4]:
mystery(5)

Odd number: 5
Even number: 2
Odd number: 3

In [5]:
mystery(8)

Even number: 8
Odd number: 9
Even number: 6
Odd number: 7
Even number: 4
Odd number: 5
Even number: 2
Odd number: 3


#### Mystery Function 2¶

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.

In [6]:
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="")

In [7]:
mystery2(4, 5)

20, 16, 12, 8, 4, 8, 12, 16, 20
In [8]:
mystery2(2, 3)

6, 4, 2, 4, 6
In [9]:
mystery2(0, 5)

0, 0, 0, 0, 0, 0, 0, 0, 0

#### Mystery Function 3¶

In [10]:
def mystery3(s):
if s == "":
return ""
else:
return mystery3(s[1:]) + s[0]

In [11]:
mystery3("bat")

Out[11]:
'tab'
In [12]:
mystery3("mystery")

Out[12]:
'yretsym'
In [13]:
mystery3("testing")

Out[13]:
'gnitset'
In [14]:
mystery3("ADA")

Out[14]:
'ADA'

Question: What slicing operation has the same behavior as mystery3?

#### Challenge: Mystery Function 4¶

Note that this one is a bit harder and is more of a challenge problem.

In [15]:
def mystery4(s):
if s == "":
return 0
elif s[0] == "1":
return 2 ** (len(s) - 1) + mystery4(s[1:])
else:
return mystery4(s[1:])

In [16]:
mystery4("1001")

Out[16]:
9
In [17]:
mystery4("10000")

Out[17]:
16
In [18]:
mystery4("1")

Out[18]:
1

Question: Can you figure out what mystery4 is computing?

In [19]:
"CS" + str(mystery4("11110000")) # Take this class to learn more :-)

Out[19]:
'CS240'

### 1.2 Writing Non-Fruitful Recursion Problems¶

#### Subtract Four¶

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
0
In [20]:
def subtractFour(num):
if num >= 0:
print(num)
subtractFour(num - 4)

In [21]:
subtractFour(4)

4
0

In [22]:
subtractFour(16)

16
12
8
4
0

In [23]:
subtractFour(144)

144
140
136
132
128
124
120
116
112
108
104
100
96
92
88
84
80
76
72
68
64
60
56
52
48
44
40
36
32
28
24
20
16
12
8
4
0


#### Count Up By Four¶

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
12
In [24]:
def countUpByFour(num):
if num >= 0:
countUpByFour(num - 1)
print(num * 4)

In [25]:
countUpByFour(3)

0
4
8
12

In [26]:
countUpByFour(10)

0
4
8
12
16
20
24
28
32
36
40

In [27]:
countUpByFour(1)

0
4

In [28]:
countUpByFour(0)

0


#### Carrot Border¶

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<<<<.

In [29]:
def carrotBorder(s, num):
if num == 0:
print(s, end="")
else:
print(">", end="")
carrotBorder(s, num - 1)
print("<", end="")

In [30]:
carrotBorder("INCEPTION", 4)

>>>>INCEPTION<<<<
In [31]:
carrotBorder("AWESOME", 9)

>>>>>>>>>AWESOME<<<<<<<<<
In [32]:
carrotBorder("COOL", 3)

>>>COOL<<<
In [33]:
carrotBorder("", 20)

>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<

#### Challenge: Hourglass Word¶

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*****
In [34]:
def hourglassWord(s, currentRow, numRows):
padding = (numRows - currentRow) * ' '
if currentRow == 0:
else:
stars = "*" * currentRow
hourglassWord(s, currentRow - 1, numRows)

In [35]:
hourglassWord("MINDBLOWING", 5, 5)

*****MINDBLOWING*****
****MINDBLOWING****
***MINDBLOWING***
**MINDBLOWING**
*MINDBLOWING*
MINDBLOWING
*MINDBLOWING*
**MINDBLOWING**
***MINDBLOWING***
****MINDBLOWING****
*****MINDBLOWING*****

In [36]:
hourglassWord("WHOA", 10, 10)

**********WHOA**********
*********WHOA*********
********WHOA********
*******WHOA*******
******WHOA******
*****WHOA*****
****WHOA****
***WHOA***
**WHOA**
*WHOA*
WHOA
*WHOA*
**WHOA**
***WHOA***
****WHOA****
*****WHOA*****
******WHOA******
*******WHOA*******
********WHOA********
*********WHOA*********
**********WHOA**********

In [37]:
hourglassWord("A", 1, 1)

*A*
A
*A*

In [38]:
hourglassWord("SAND", 30, 30)

******************************SAND******************************
*****************************SAND*****************************
****************************SAND****************************
***************************SAND***************************
**************************SAND**************************
*************************SAND*************************
************************SAND************************
***********************SAND***********************
**********************SAND**********************
*********************SAND*********************
********************SAND********************
*******************SAND*******************
******************SAND******************
*****************SAND*****************
****************SAND****************
***************SAND***************
**************SAND**************
*************SAND*************
************SAND************
***********SAND***********
**********SAND**********
*********SAND*********
********SAND********
*******SAND*******
******SAND******
*****SAND*****
****SAND****
***SAND***
**SAND**
*SAND*
SAND
*SAND*
**SAND**
***SAND***
****SAND****
*****SAND*****
******SAND******
*******SAND*******
********SAND********
*********SAND*********
**********SAND**********
***********SAND***********
************SAND************
*************SAND*************
**************SAND**************
***************SAND***************
****************SAND****************
*****************SAND*****************
******************SAND******************
*******************SAND*******************
********************SAND********************
*********************SAND*********************
**********************SAND**********************
***********************SAND***********************
************************SAND************************
*************************SAND*************************
**************************SAND**************************
***************************SAND***************************
****************************SAND****************************
*****************************SAND*****************************
******************************SAND******************************


### 1.3 Writing Fruitful Recursion Problems¶

#### Power¶

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.

In [39]:
def toPowerOf(x, n):
if n == 0:
return 1
else:
return x * toPowerOf(x, n - 1)

In [40]:
toPowerOf(3, 4) # should return 81

Out[40]:
81
In [41]:
toPowerOf(5, 7) # should return 78125

Out[41]:
78125
In [42]:
toPowerOf(0, 3) # should return 0

Out[42]:
0

#### Sum of Squares¶

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.

In [43]:
def sumOfSquares(n):
if n == 0:
return 0
else:
return n ** 2 + sumOfSquares(n - 1)

In [44]:
sumOfSquares(0) # Should return 0

Out[44]:
0
In [45]:
sumOfSquares(2) # Should return 5

Out[45]:
5
In [46]:
sumOfSquares(5) # Should return 55

Out[46]:
55
In [47]:
sumOfSquares(85) # Should return 208335

Out[47]:
208335

#### Count Vowels¶

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.

In [48]:
def isVowel(letter):
return letter.lower() in "aeiou"

def countVowels(word):
if word == "":
return 0
elif isVowel(word[0]):
return 1 + countVowels(word[1:])
else:
return countVowels(word[1:])

In [49]:
countVowels("beauteous") # should return 6

Out[49]:
6
In [50]:
countVowels("precarious") # should return 5

Out[50]:
5
In [51]:
countVowels("") # should return 0

Out[51]:
0
In [52]:
countVowels("gfh") # should return 0

Out[52]:
0

#### List of End Strings¶

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"].

In [53]:
def listOfEndStrings(s):
if s == "":
return []
else:
return listOfEndStrings(s[1:]) + [s]

In [54]:
listOfEndStrings("abcde")

Out[54]:
['e', 'de', 'cde', 'bcde', 'abcde']
In [55]:
listOfEndStrings("Andy")

Out[55]:
['y', 'dy', 'ndy', 'Andy']
In [56]:
listOfEndStrings("y")

Out[56]:
['y']

#### Challenge: Is It A Palindrome?¶

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.

In [57]:
def isPalindrome(word):
if word == "":
return True
elif word[0] != word[-1]:
return False
else:
return isPalindrome(word[1:-1])

In [58]:
isPalindrome("racecar") # should return True

Out[58]:
True
In [59]:
isPalindrome("tenet") # should return True

Out[59]:
True
In [60]:
isPalindrome("Andy") # should return False

Out[60]:
False
In [61]:
isPalindrome("abcdba") # should return False

Out[61]:
False

## 2. Challenge "Choose-it-or-lose-it" Problems¶

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.

#### Longest Common Subsequence¶

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.

In [62]:
def longestCommonSubsequence(word1, word2):
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

In [63]:
longestCommonSubsequence("rat", "at") # should return "at"

Out[63]:
'at'
In [64]:
longestCommonSubsequence("asp", "ap") # should return "ap"

Out[64]:
'ap'
In [65]:
longestCommonSubsequence("art", "") # should return ""

Out[65]:
''
In [66]:
longestCommonSubsequence("locomotion", "elocution") # should return "loction"

Out[66]:
'loction'
In [67]:
longestCommonSubsequence("grandiose", "splendor") # should return "ndo"

Out[67]:
'ndo'
In [68]:
longestCommonSubsequence("", "") # should return ""

Out[68]:
''

#### String Permutations¶

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.

In [69]:
def stringPermutations(word):
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)

In [70]:
stringPermutations("ABC")

ABC
ACB
BAC
BCA
CBA
CAB

In [71]:
stringPermutations("Andy")

Andy
Anyd
Aydn
Aynd
nAyd
ndAy
ndyA
nydA