Look at this recursive function repeatPrint()
. Notice how there are no loops!
def repeatPrint(text, howManyTimes):
if howManyTimes == 0:
return
else:
print(text)
repeatPrint(text, howManyTimes - 1)
repeatPrint('Hello AddisCoder', 3)
repeatPrint('Recursion is the best', 8)
Hello AddisCoder Hello AddisCoder Hello AddisCoder Recursion is the best Recursion is the best Recursion is the best Recursion is the best Recursion is the best Recursion is the best Recursion is the best Recursion is the best
What is the recursive case for repeatPrint()
? Please use English.
# YOUR ANSWER HERE
What is the base case for repeatPrint()
? Please use English.
# YOUR ANSWER HERE
Consider a recursive function called sumAll(lst)
.
lst
, as input.For example:
sumAll([1, 1, 1]) == 3
sumAll([1, 2, 3]) == 6
sumAll([]) == 0
sumAll([1, -1]) == 0
What is the recursive case for sumAll()
? Describe your answer using English.
# YOUR ANSWER HERE
What is the base case for sumAll()
? Use English.
# YOUR ANSWER HERE
Use your base case and recursive case to write a sumAll()
function
def sumAll(lst):
# YOUR ANSWER HERE
return
# After you finish, these should all print True
print(sumAll([1, 1, 1]) == 3)
print(sumAll([1, 2, 3]) == 6)
print(sumAll([]) == 0)
print(sumAll([1, -1]) == 0)
False False False False
Consider a recursive function called numTimes(s, letter)
:
s
and a single letter letter
.letter
appears in s
.For example:
numTimes('aaabbaaab', 'b') == 3
numTimes('aaabbaaab', 'a') == 6
numTimes('c', 'c') == 1
numTimes('abcd', 'e') == 0
numTimes('', 'a') == 0
What is the recursive case for numTimes()
?
# YOUR ANSWER HERE
What is the base case for numTimes()
?
# YOUR ANSWER HERE
Write a numTimes()
function using your base and recursive cases.
def numTimes(s, letter):
# YOUR CODE HERE
return
# After you finish, these should all print True
print(numTimes('aaabbaaab', 'b') == 3)
print(numTimes('aaabbaaab', 'a') == 6)
print(numTimes('c', 'c') == 1)
print(numTimes('abcd', 'e') == 0)
print(numTimes('', 'a') == 0)
False False False False False
Use recursion to write an exponential function, exp(a, b)
, that calculates $a^b$.
Some examples:
exp(5, 2) == 25
exp(5, 3) == 125
exp(2, 3) == 8
exp(1, 100) == 1
exp(5, 0) == 1
exp(123, 0) == 1
Assume:
Under these assumptions, we know two things about $a^b$:
Looking at the math above, what is the recursive case for exp(a, b)
?
# YOUR ANSWER HERE
What is the base case for exp(a, b)
?
# YOUR ANSWER HERE
Write code for exp(a, b)
def exp(a, b):
# YOUR CODE HERE
return
# After you finish, these should all print True
print(exp(5, 2) == 25)
print(exp(5, 3) == 125)
print(exp(2, 3) == 8)
print(exp(1, 100) == 1)
print(exp(5, 0) == 1)
print(exp(171, 0) == 1)
False False False False False False
Make a recursive function called reverse(s)
that takes a string, s
, and reverses it.
For example:
reverse('abc') == 'cba'
reverse('ccc') == 'ccc'
reverse('this is a long string') == 'gnirts gnol a si siht'
reverse('') == ''
What is the recursive case for reverse(s)
?
# YOUR ANSWER HERE
What is the base case for reverse(s)
?
# YOUR ANSWER HERE
Write code for reverse(s)
def reverse(s):
# YOUR CODE HERE
return
# After you finish, these should all print True
print(reverse('abc') == 'cba')
print(reverse('ccc') == 'ccc')
print(reverse('this is a long string') == 'gnirts gnol a si siht')
print(reverse('') == '')
False False False False
Define a recursive function removeLetter(s, letter)
which:
s
and a single character letter
.def removeLetter(s, letter):
# YOUR CODE HERE
return
# After you finish, these should all print True
print(removeLetter('abc', 'a') == 'bc')
print(removeLetter('abaca', 'a') == 'bc')
print(removeLetter('abc', 'd') == 'abc')
print(removeLetter('', 'a') == '')
print(removeLetter('letter', 't') == 'leer')
False False False False False
Define a recursive function called sumDigits(n)
which:
n
as an argument. Assume n >= 0
.n
. For example:sumDigits(111) == 3 # because 1 + 1 + 1 == 3
sumDigits(123) == 5 # because 1 + 2 + 3 == 5
sumDigits(505) == 10 # because 5 + 0 + 5 == 10
Hint: use the %
and //
operators
def sumDigits(n):
# YOUR CODE HERE
return
# After you finish, these should all print True
print(sumDigits(111) == 3)
print(sumDigits(123) == 3)
print(sumDigits(505) == 3)
print(sumDigits(123456789) == 45)
print(sumDigits(0) == 0)
False False False False False
Write a recursive function gcd(a, b)
that:
a
and b
as input.a
and b
.For example:
gcd(15, 10) == 5 # nothing bigger than 5 divides 15 and 10.
gcd(24, 36) == 12
gcd(72, 180) == 36
gcd(101, 197) == 1 # 101 and 197 do not share any common factors.
gcd(39793, 1) == 1 # gcd(a, 1) == 1 for all positive a.
gcd(22, 0) == 22 # gcd(a, 0) == a for all positive a.
To implement gcd()
, we will use a recursive algorithm that Euclid discovered in Alexandria, Egypt in 300BC. Here it is:
If $b > 0$,
gcd(a, b) == gcd(b, a % b)
gcd(a, 0) == a
Here is an example of Euclid's algorithm for gcd(180, 72)
:
# Recursive case: 180 % 72 == 36
gcd(180, 72) == gcd(72, 36)
# Recursive case: 72 % 36 == 0
gcd(72, 36) == gcd(36, 0)
# Base case (b == 0)
gcd(36, 0) == 36
Result: the greatest common divisor of 180 and 72 is 36.
Here is another example, of gcd(45, 210)
:
# Recursive case: 45 % 210 == 45
gcd(45, 210) == gcd(210, 45)
# Recursive case: 210 % 45 == 30
gcd(210, 45) == gcd(45, 20)
# Recursive case: 45 % 30 == 15
gcd(45, 30) == gcd(30, 15)
# Recursive case: 30 % 15 = 0
gcd(30, 15) == gcd(15, 0)
# Base case (b == 0)
gcd(15, 0) == 15
Result: the greatest common divisor of 45 and 210 is 15.
Using Euclid's algorithm, write code for gcd(a, b)
def gcd(a, b):
# YOUR CODE HERE
return
# After you finish, these should all print True
print(gcd(15, 10) == 5)
print(gcd(24, 36) == 12)
print(gcd(72, 180) == 36)
print(gcd(101, 197) == 1)
print(gcd(39793, 1) == 1)
print(gcd(22, 0) == 22)
False False False False False False
Fibonacci numbers have many applications in nature and math. Here are the first 10 Fibonacci numbers:
fib(0) == 0
fib(1) == 1
fib(2) == 1
fib(3) == 2
fib(4) == 3
fib(5) == 5
fib(6) == 8
fib(7) == 13
fib(8) == 21
fib(9) == 34
...
Can you see a pattern? Using math, we can define the $n^{th}$ Fibonacci number, $F(n)$, using a recurrence:
$F(0) = 0$
$F(1) = 1$
and for $n >= 2$:
$F(n) = F(n - 1) + F(n - 2)$
Write code to find the $n^{th}$ Fibonacci number.
def fib(n):
# YOUR CODE HERE
return
# When you finish, these should all print True
print(fib(0) == 0)
print(fib(1) == 1)
print(fib(2) == 1)
print(fib(3) == 2)
print(fib(6) == 8)
print(fib(9) == 34)
print(fib(20) == 6765)
False False False False False False False
The decimal number system (base 10) is a common way to write numbers. Here we will explore the binary number system (base 2) which has many applications in computing.
To give an example, 128 in decimal is written as 10000000 in binary. Here is why:
In decimal (base 10),
$128 = 1 \cdot 10^2 + 2 \cdot 10^1 + 8 \cdot 10^0$
and in binary (base 2),
$128 = 1 \cdot 2^6 + 0 \cdot 2^5 + \dots + 0 \cdot 2^0$
Here is another example. 39 is 100111 in binary:
In decimal,
$39 = 3 \cdot 10^1 + 9 \cdot 10^0$
and in binary,
$39 = 1 \cdot 2^5 + 0 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0$
Write a recursive function, binaryString(n)
, that:
n
, as input.Hint: In python, str(n)
converts a number to a string.
str(1) == '1'
str(55) == '55'
def binaryString(n):
# YOUR CODE HERE
return
# After you finish, these should print True
testCases = [
[0, '0'],
[1, '1'],
[2, '10'],
[1, '1'],
[2, '10'],
[3, '11'],
[4, '100'],
[5, '101'],
[6, '110'],
[7, '111'],
[8, '1000'],
[39, '100111'],
[128, '10000000'],
[297371, '1001000100110011011'],
]
for arg, result in testCases:
print(binaryString(arg) == result)
False False False False False False False False False False False False False False
Write a recursive function decimalNumber(binString)
that converts a binary string binString
into its corresponding decimal number.
Hint: In Python, int(decimalString)
converts a string into an integer:
int('0') == 0
int('44') == 44
def decimalNumber(binString):
# YOUR CODE HERE
return None
testCases = [
['0', 0],
['1', 1],
['10', 2],
['1', 1],
['10', 2],
['11', 3],
['100', 4],
['101', 5],
['110', 6],
['111', 7],
['1000', 8],
['100111', 39],
['10000000', 128],
['1001000100110011011', 297371],
]
for arg, result in testCases:
print(decimalNumber(arg) == result)
print(decimalNumber(binaryString(12278)) == 12278)
print(binaryString(decimalNumber('100111')) == '100111')
False False False False False False False False False False False False False False False False
In mathematics, a permutation of a list is the same list, but in a different order.
For example, [0, 2, 1]
and [2, 0, 1]
are both permutations of [0, 1, 2]
.
Write a recursive function permutations(n)
that takes an integer, n
, as input, and returns a sorted list of all permutations of integers between 0
and n
. Examples:
permutations(0) == [[0]]
permutations(1) == [[0, 1], [1, 0]]
permutations(2) == [[0, 1, 2], [0, 2, 1],
[1, 0, 2], [1, 2, 0],
[2, 0, 1], [2, 1, 0]]
Hints
myList.insert(5, 'myItem')
will insert 'myItem'
at position 5
in myList
.sort(myList)
to put myList
in sorted order. Note: sort()
returns None
, so use it on its own line of code.# Example code: insert() and sort()
myList = [2, 0, 3, 1]
myList.insert(2, 77) # insert 77 at position 2 in myList
print("myList hasn't been sorted yet:", myList)
myList.sort()
print("Now myList is sorted:", myList)
myList hasn't been sorted yet: [2, 0, 77, 3, 1] Now myList is sorted: [0, 1, 2, 3, 77]
Write a recursive permutations(n)
function. Remember: it is OK to use loops in Question 10!
def permutations(n):
return
# If your code is correct, these should all print True
print(permutations(0) == [[0]])
print(permutations(1) == [[0, 1], [1, 0]])
print(permutations(2) == [[0, 1, 2], [0, 2, 1],
[1, 0, 2], [1, 2, 0],
[2, 0, 1], [2, 1, 0]])
if permutations(0) != None:
print(len(permutations(6)) == 5040)
print(permutations(6)[3791] == [5, 1, 3, 6, 4, 2, 0])
else:
print(False)
False False False False