[12.1] Write a function countAs that takes a string as parameter and that recursively counts how many “a” or “A” characters are in the string. The function returns this count. For example countAs("AbrAcadAbra") should return 5.
def countAs(s):
# Base case: if the string is empty, return 0
if len(s) == 0:
return 0
else:
smallerProblem = s[1:] # Make the problem one smaller
smallerResult = countAs(smallerProblem) # Call the recursive genie
# Check the first character of the string
# If it's 'a' or 'A', add 1, else 0
if s[0] == "a" or s[0] == "A":
return smallerResult + 1
else:
return smallerResult
# Example usage:
input_string = "AbrAcadAbra"
result = countAs(input_string)
print(result)
[12.2] Write the function remove99s(lst) that takes a list of items and recursively generates a new list without including the number 99 but including every original item otherwise. For example, removeDuplicates([1, 99, 99, 2, 99, 4, 99, 3]) might return [1, 2, 4, 3].
def remove99s(lst):
# Base case: if the list is empty, return an empty list
if lst == []:
return []
else:
smallerProblem = lst[1:]
smallerResult = remove99s(smallerProblem)
# If the first element is 99, skip it and return the smallerResult
if lst[0] == 99:
return smallerResult
# If the first element is not 99, include it in the smallerResult which is a list
else:
return [lst[0]] + smallerResult
# Example usage:
input_list = [1, 99, 99, 2, 99, 4, 99, 3]
result = remove99s(input_list)
print("The list without 99s is: ", result)
[12.3] Write recursiveMatch(lst1, lst2), which takes two lists of equal length and returns the number of indexes where lst1 has the same value as lst2. For example, recursiveMatch([4, 2, 1, 6], [4, 3, 7, 6]) should return 2.
def recursiveMatch(lst1, lst2):
# Base case: if the lists are empty, return 0
if lst1 == [] or lst2 == []:
return 0
else:
smallerResult = recursiveMatch(lst1[1:], lst2[1:])
if lst1[0] == lst2[0]:
return 1 + smallerResult
else:
return smallerResult
# Example usage:
list1 = [4, 2, 1, 6]
list2 = [4, 3, 7, 6]
result = recursiveMatch(list1, list2)
print("The number of matching indexes is: ", result)
[12.4] Write a recursive function called checkPal that takes a string as a parameter and returns True if the given string is a palindrome or False otherwise.
def checkPal(s):
# Base case: if the string is empty or has only one character, it's a palindrome
if len(s) <= 1:
return True
else:
smallerProblem = s[1:len(s)-1]
smallerResult = checkPal(smallerProblem)
# Check if the first and last characters are equal
if s[0] == s[len(s)-1]:
return smallerResult # if equal, return smallerResult
else:
return False # not a plaindrome
# Example usage:
print(checkPal("radar")) # True
print(checkPal("abcdefghhgfedcba")) # True
print(checkPal("hello")) # False
[12.5] Write a recursive function called findSum that takes a positive integer as a parameter and returns the sum of all its digits.
def findSum(n):
# Base case: if the number has only one digit, return the number itself
if n < 10:
return n
else:
smallerProblem = n // 10
smallerResult = findSum(smallerProblem)
last_digit = n % 10
return last_digit + smallerResult
# Example usage:
print(findSum(12345)) # 15
[12.6] Create a recursive function called raisePow that takes two integers, b and e and calculates the result of raising the base b to the exponent e.
def raisePow(b, e):
# Base case: if the exponent is 0, the result is 1
if e == 0:
return 1
# Recursive case: multiply the base by the result of raising the base to (e - 1)
return b * raisePow(b, e - 1)
# Example usage:
print(raisePow(2, 3))
[12.7] Use recursion to write reverseEvens(), a function that takes in a list L and returns all the evens in L in the reverse order in which they originally appeared:
def reverseEvens(L):
# Base Case: when the list is empty
if L == []:
return []
# Recursive case: if L[0] is even then add it to the end of the recursive result otherwise simply return the recursive result (recursive call on smaller list)
else:
if L[0] % 2 == 0:
return reverseEvens(L[1:]) + [L[0]]
return reverseEvens(L[1:])
# Example usage:
assert(reverseEvens([1,2,3,4,5,6]) == [6,4,2])
assert(reverseEvens([2,10,18]) == [18,10,2])
assert(reverseEvens([14,15,4,16,2]) == [2,16,4,14])
[12.8] Use recursion to write sumDigits(), a function which finds the sum of all digits of a positive number n. Do not use strings.
def sumDigits(n):
# Base Case: if n is 0 => simply return 0
if n == 0:
return 0
else:
# Recursive Case: Get the last digit and add it to the result of the recursive call on all digits except the last.
num = n % 10 # this will get us the digit in units place
smallerProblem = n // 10 # this will get us all the digits except the last one
return num + sumDigits(smallerProblem)
# Example usage:
assert(sumDigits(1234) == 10)
assert(sumDigits(111) == 3)
assert(sumDigits(0) == 0)
[12.9] Write a recursive function that takes in a list of integers and returns the maximum value stored in the list.
def maxVal(L):
# Base case: if there is only 1 element in the list, that must be the max element
if len(L) == 1:
return L[0]
else:
# Recursive case: maximum is either the first value in the list or the maximum of the rest of the list
smallerLsit = L[1:]
smallerResult = maxVal(L[1:])
if L[0] > smallerResult:
return L[0]
else:
return smallerResult
# Example usage:
print(maxVal([1, 5, 8, 3, 9])) # Output: 9
[12.10] Write a recursive function checkMatch that takes in two strings and returns a count of the number of characters where the two strings' indices do not match. This function is case sensitive so “H’ != “h”. The length of the strings will be the same.
def checkMatch(s1, s2):
# Base Case: if either of the strings are empty we just return 0
if len(s1) == 0 or len(s2) == 0:
return 0
# Recursive Case:
else:
smallerResult = checkMatch(s1[1:], s2[1:])
# Add 1 to the recursive result if the first two characters of the string do not match
if s1[0] != s2[0]:
return 1 + smallerResult
# Otherwise simply return the recursive result
return smallerResult
# Example usage:
print(checkMatch("hello", "HellO")) # Output: 2
[12.11] Write a recursive function that given a string and a substring, calculates the number of times that substring appears in the string. You are guaranteed that the length of the string will be a multiple of the substring and the substrings will not overlap.
def strCount(s, substring):
# Base Case: if the string is empty
if len(s) == 0:
return 0
# Recursive Case: check if substring matches and add 1 to recursive result if match otherwise just return recursive call's result
else:
if s[0:len(substring)] == substring:
# If it is a match we can remove the substring we matched in our smaller problem
return 1 + strCount(s[len(substring):], substring)
# If it is not a match, we continue to check the rest of the string
return strCount(s[1:], substring)
# Example usage:
print(strCount("catcowcat", "cat")) # Output: 2
[12.12] Write a recursive function addPows that takes in a list of numbers and returns a new list of numbers where each element is calculated by raising the respective element from the original list to it’s own power.
def addPows(L):
# Base case is when the list is empty
if len(L) == 0:
return []
# Recursive Case: Add the answer for L[0] in a list to the recursive result
else:
return [L[0] ** L[0]] + addPows(L[1:])
# Example usage:
print(addPows([1, 3, 5])) # Output: [1, 27, 3125]
[12.13] Write a recursive function that takes in two lists and returns a list of the absolute value difference between each element of the lists that is at the same index. You are guaranteed that the length of the lists will be the same.
def list_difference(L1, L2):
# Base case is if the lists are both empty
if L1 == []:
return []
# Recursive Case: calculate the absolute difference and add it to the recursive result in a list
else:
return [abs(L1[0] - L2[0])] + list_difference(L1[1:], L2[1:])
# Example usage:
list1 = [1, 2, 3, 4]
list2 = [5, 3, 2, 1]
print(list_difference(list1, list2)) # Output: [4, 1, 1, 3]