In essence, recursion is a method of solving problems where the overall solution depends on solutions to smaller instances of the same problem (subproblems). In the context of programming, this would involve a function calling itself with different arguments that describe the subproblem.
The basic structure of a recursive function is:
def recursive_function(parameters):
if base_case_condition(parameters):
return base_case_value
return recursive_function(modified_parameters)
Remember, although recursion can be an effective approach for many problems, it's not always the best choice. Recursive solutions are usually short to write, though often less efficient than iterative solutions (i.e. those that use for
or while
loops).
Functions in Python have a recursion limit, usually set to 1000. If you exceed this limit, Python will raise a RecursionError. You can check your recursion limit with sys.getrecursionlimit()
, and change it with sys.setrecursionlimit()
, but it's generally not a good idea to change the limit.
For the following problems, feel free (and we strongly encourage you) to add your own test cases. We have provided a few test cases (e.g. sumAll([1, 2, 3]) == 6
for Q1), but you should add more to ensure your code is working properly.
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.
# 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.
# Describe your answer in English
What is the base case for sumAll()
? Use English.
# Describe your answer in English
Use your base case and recursive case to write a sumAll()
function
def sumAll(lst):
# YOUR ANSWER HERE
pass
# 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()
?
# Describe your answer in English
What is the base case for numTimes()
?
# Describe your answer in English
Write a numTimes()
function using your base and recursive cases.
def numTimes(s, letter):
# YOUR ANSWER HERE
pass
# 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)
?
# Describe your answer in English
What is the base case for exp(a, b)
?
# Describe your answer in English
Write code for exp(a, b)
def exp(a, b):
# YOUR ANSWER HERE
pass
# 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)
?
# Describe your answer in English
What is the base case for reverse(s)
?
# Describe your answer in English
Write code for reverse(s)
def reverse(s):
# YOUR ANSWER HERE
pass
# 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 ANSWER HERE
pass
# 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) == 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
pass
# 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)
False False False False False
Consider a recursive function called factorial(num)
:
For example:
factorial(0) == 0
factorial(1) == 1
factorial(3) == 6
factorial(5) == 120
factorial(10) == 3628800
Implement the recursive function factorial(num)
.
def factorial(num):
# your code here
pass
# after you finish, these all should print true
print('Test passed:', factorial(0) == 1)
print('Test passed:', factorial(1) == 1)
print('Test passed:', factorial(2) == 2)
print('Test passed:', factorial(3) == 6)
print('Test passed:', factorial(5) == 120)
Test passed: False Test passed: False Test passed: False Test passed: False Test passed: False
Consider a recursive function called palindromeCheck(word)
:
For example:
palindromeCheck("racecar") == True
palindromeCheck("hello") == False
palindromeCheck("level") == True
palindromeCheck("python") == False
Implement palindromeCheck(word)
.
def palindromeCheck(n):
# your code here
pass
# after you finish, these all should print true
print('Test passed:', palindromeCheck("racecar") == True)
print('Test passed:', palindromeCheck("hello") == False)
print('Test passed:', palindromeCheck("level") == True)
print('Test passed:', palindromeCheck("python") == False)
Test passed: False Test passed: False Test passed: False Test passed: False
Consider a recursive function called countDigits(n)
:
n
.n
.For example:
countDigits(0) == 1
countDigits(123) == 3
countDigits(987654321) == 9
Implement countDigits(n)
.
def countDigits(n):
# your code here
pass
# after you finish, these all should print true
print('Test passed:', countDigits(0) == 1)
print('Test passed:', countDigits(123) == 3)
print('Test passed:', countDigits(987654321) == 9)
Test passed: False Test passed: False Test passed: False
Consider a recursive function called sumRange(a, b)
:
For example:
sumRange(0, 0) == 0
sumRange(1, 5) == 15 # (1 + 2 + 3 + 4 + 5)
sumRange(10, 15) == 75 # (10 + 11 + 12 + 13 + 14 + 15)
sumRange(5, 10) == 45 # (5 + 6 + 7 + 8 + 9 + 10)
Implement sumRange(a, b)
.
def sumRange(a, b):
# your code here
pass
# after you finish, these all should print true
print('Test passed:', sumRange(0, 0) == 0)
print('Test passed:', sumRange(1, 5) == 15)
print('Test passed:', sumRange(10, 15) == 75)
print('Test passed:', sumRange(5, 10) == 45)
Test passed: False Test passed: False Test passed: False Test passed: False