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

End.