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)
What is the recursive case for repeatPrint()
? Please use English.
# recursive case is a branch of the conditional statement in a recursive function that results in a recursive call.
# for the above the recursive case is: repeatPrint(text, howManyTimes - 1)
What is the base case for repeatPrint()
? Please use English.
# base case is a branch of the conditional statement in a recursive function that does not result in a recursive call.
# for the above the base case is: if howManyTimes == 0:
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.
What is the base case for sumAll()
? Use English.
Use your base case and recursive case to write a sumAll()
function
def sumAll(lst):
# YOUR ANSWER HERE
# 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)
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()
?
What is the base case for numTimes()
?
Write a numTimes()
function using your base and recursive cases.
def numTimes(s, letter):
# YOUR ANSWER HERE
# 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)
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)
?
What is the base case for exp(a, b)
?
Write code for exp(a, b)
def exp(a, b):
# YOUR ANSWER HERE
# 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)
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)
?
What is the base case for reverse(s)
?
Write code for reverse(s)
def reverse(s):
# YOUR ANSWER HERE
# 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('') == '')
Define a recursive function removeLetter(s, letter)
which:
s
and a single character letter
.def removeLetter(s, letter):
# YOUR ANSWER HERE
# 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')
;
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) == 6 # because 1 + 2 + 3 == 6
sumDigits(505) == 10 # because 5 + 0 + 5 == 10
Hint: use the %
and //
operators
def sumDigits(n):
# YOUR ANSWER HERE
# After you finish, these should all print True
print(sumDigits(111) == 3)
print(sumDigits(123) == 6)
print(sumDigits(505) == 10)
print(sumDigits(123456789) == 45)
print(sumDigits(0) == 0)
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 ANSWER HERE
# 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)
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 ANSWER HERE
# 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)
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 ANSWER HERE
# 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)
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 ANSWER HERE
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')
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)
Write a recursive permutations(n)
function. Remember: it is OK to use loops in Question 10!
def permutations(n):
# YOUR ANSWER HERE
# 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)