Bonus Challenging Recursion Problems
Note : If you're new to Data Structures and Algorithms in Python, it's a good idea to skip this part for now and come back after you've completed all the data structures sections.
power
Write a function called power which accepts a base and an exponent. The function should return the power of the base to the exponent. This function should mimic the functionality of math.pow() - do not worry about negative bases and exponents.
Examples
power(2,0) # 1power(2,2) # 4power(2,4) # 16
def power(base, exponent):
if exponent == 0:
return 1
return base * power(base, exponent-1)
factorial
Write a function factorial which accepts a number and returns the factorial of that number. A factorial is the product of an integer and all the integers below it; e.g., factorial four ( 4! ) is equal to 24, because 4 3 2 * 1 equals 24. factorial zero (0!) is always 1.
Examples
factorial(1) # 1factorial(2) # 2factorial(4) # 24factorial(7) # 5040
def factorial(num):
if num <= 1:
return 1
return num * factorial(num-1)
productofArray
Write a function called productOfArray
which takes in an array of numbers and returns the product of them all.
Examples
productOfArray([1,2,3]) #6productOfArray([1,2,3,10]) #60
def productOfArray(arr):
if len(arr) == 0:
return 1
return arr[0] * productOfArray(arr[1:])
recursiveRange
Write a function called recursiveRange which accepts a number and adds up all the numbers from 0 to the number passed to the function.
Examples
recursiveRange(6) # 21recursiveRange(10) # 55
def recursiveRange(num):
if num <= 0:
return 0
return num + recursiveRange(num - 1)
fib
Write a recursive function called fib which accepts a number and returns the nth number in the Fibonacci sequence. Recall that the Fibonacci sequence is the sequence of whole numbers 0,1, 1, 2, 3, 5, 8, ... which starts with 0 and 1, and where every number thereafter is equal to the sum of the previous two numbers.
Examples
fib(4) # 3fib(10) # 55fib(28) # 317811fib(35) # 9227465
def fib(num):
if (num < 2):
return num
return fib(num - 1) + fib(num - 2)
reverse
Write a recursive function called reverse which accepts a string and returns a new string in reverse.
Examples
reverse('python') # 'nohtyp'reverse('appmillers') # 'srellimppa'
def reverse(strng):
if len(strng) <= 1:
return strng
return strng[len(strng)-1] + reverse(strng[0:len(strng)-1])
isPalindrome
Write a recursive function called isPalindrome which returns true if the string passed to it is a palindrome (reads the same forward and backward). Otherwise it returns false.
Examples
isPalindrome('awesome') # falseisPalindrome('foobar') # falseisPalindrome('tacocat') # trueisPalindrome('amanaplanacanalpanama') # trueisPalindrome('amanaplanacanalpandemonium') # false
def isPalindrome(strng):
if len(strng) == 0:
return True
if strng[0] != strng[len(strng)-1]:
return False
return isPalindrome(strng[1:-1])
someRecursive
Write a recursive function called someRecursive which accepts an array and a callback. The function returns true if a single value in the array returns true when passed to the callback. Otherwise it returns false.
Examples
someRecursive([1,2,3,4], isOdd) # truesomeRecursive([4,6,8,9], isOdd)
# truesomeRecursive([4,6,8], isOdd) # false
def someRecursive(arr, cb):
if len(arr) == 0:
return False
if not(cb(arr[0])):
return someRecursive(arr[1:], cb)
return True
def isOdd(num):
if num%2==0:
return False
else:
return True
flatten
Write a recursive function called flatten which accepts an array of arrays and returns a new array with all values flattened.
Examples
flatten([1, 2, 3, [4, 5]]) # [1, 2, 3, 4, 5]flatten([1, [2, [3, 4], [[5]]]])
# [1, 2, 3, 4, 5]flatten([[1], [2], [3]])
# [1, 2, 3]flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]])
# [1, 2, 3]
def flatten(arr):
resultArr = []
for custItem in arr:
if type(custItem) is list:
resultArr.extend(flatten(custItem))
else:
resultArr.append(custItem)
return resultArr
captalizeFirst
Write a recursive function called capitalizeFirst. Given an array of strings, capitalize the first letter of each string in the array.
Example
capitalizeFirst(['car', 'taco', 'banana']) # ['Car','Taco','Banana']
def capitalizeFirst(arr):
result = []
if len(arr) == 0:
return result
result.append(arr[0][0].upper() + arr[0][1:])
return result + capitalizeFirst(arr[1:])
nestedEvenSum
Write a recursive function called nestedEvenSum. Return the sum of all even numbers in an object which may contain nested objects.
Examples
obj1 = { "outer": 2, "obj": { "inner": 2, "otherObj": { "superInner": 2, "notANumber": True, "alsoNotANumber": "yup" } }} obj2 = { "a": 2, "b": {"b": 2, "bb": {"b": 3, "bb": {"b": 2}}}, "c": {"c": {"c": 2}, "cc": 'ball', "ccc": 5}, "d": 1, "e": {"e": {"e": 2}, "ee": 'car'}} nestedEvenSum(obj1) # 6nestedEvenSum(obj2) # 10
obj1 = {
"outer": 2,
"obj": {
"inner": 2,
"otherObj": {
"superInner": 2,
"notANumber": True,
"alsoNotANumber": "yup"
}
}
}
obj2 = {
"a": 2,
"b": {"b": 2, "bb": {"b": 3, "bb": {"b": 2}}},
"c": {"c": {"c": 2}, "cc": 'ball', "ccc": 5},
"d": 1,
"e": {"e": {"e": 2}, "ee": 'car'}
}
def nestedEvenSum(obj, sum=0):
#todo
for key in obj:
if type(obj[key]) is dict:
sum += nestedEvenSum(obj[key])
elif type(obj[key]) is int and obj[key]%2==0:
sum+=obj[key]
return sum
capitalizeWords
Write a recursive function called capitalizeWords. Given an array of words, return a new array containing each word capitalized.
Examples
words = ['i', 'am', 'learning', 'recursion']capitalizeWords(words) # ['I', 'AM', 'LEARNING', 'RECURSION']
def capitalizeWords(arr):
result = []
if len(arr) == 0:
return result
result.append(arr[0].upper())
return result + capitalizeWords(arr[1:])
stringifyNumbers
Write a function called stringifyNumbers which takes in an object and finds all of the values which are numbers and converts them to strings. Recursion would be a great way to solve this!
Examples
obj = { "num": 1, "test": [], "data": { "val": 4, "info": { "isRight": True, "random": 66 } }} stringifyNumbers(obj) {'num': '1', 'test': [], 'data': {'val': '4', 'info': {'isRight': True, 'random': '66'} }}
def stringifyNumbers(obj):
newObj = obj
for key in newObj:
if type(newObj[key]) is int:
newObj[key] = str(newObj[key])
if type(newObj[key]) is dict:
newObj[key] = stringifyNumbers(newObj[key])
return newObj
collectStrings
Write a function called collectStrings which accepts an object and returns an array of all the values in the object that have a typeof string.
Examples
obj = { "stuff": 'foo', "data": { "val": { "thing": { "info": 'bar', "moreInfo": { "evenMoreInfo": { "weMadeIt": 'baz' } } } } }} collectStrings(obj) # ['foo', 'bar', 'baz']
def collectStrings(obj):
resultArr = []
for key in obj:
if type(obj[key]) is str:
resultArr.append(obj[key])
if type(obj[key]) is dict:
resultArr = resultArr + collectStrings(obj[key])
return resultArr