recursion-practice-answers.md

Recursion Practice - Answers

factorial(n) - This function returns n!, the factorial of n. For instance, factorial(5) should return 120.

 def factorial(n):
   if n == 1:
     return 1
   else:
     return n * factorial(n-1)

sumList(L) - This function returns the sum of L, a list of integers. Hint: when recursing on a list, we often use a list of length 0 or 1 as the base case. For the general case we often try to go from a list of length n to a list of length n-1.

 def sumList(L):
   if len(L) == 0:
     return 0
   else:
     return L[0] + sumList(L[1:])

maxInList(L) - This function returns the largest value in L, a list of integers.

 def maxInList(L):
   if len(L) == 1:
     return L[0]
   else:
     maxOfRest = maxInList(L[1:])
     if L[0] > maxOfRest:
       return L[0]
     else:
       return maxOfRest

blastoff(n) - This function simulates a countdown to a rocket blasting off. If you call blastoff(5) you should see the following output:

5...
4...
3...
2...
1...
BLASTOFF!!!

This is the first example we've seen of a recursive function called for its side effects, not for its return value. Still, you should approach this problem by looking for a base case and for how you can reduce the general problem into a smaller sub-problem.

 def blastoff(n):
   if n == 0:
     print("BLASTOFF!!!")
   else:
     print("%d..." % n)
     blastoff(n-1)

getYNResponse() - This function should repeatedly prompt a user to enter 'y' or 'n', until they actually enter 'y' or 'n'. We have written this function before using a while loop. How can you replace the while loop with a recursive call?

 def getYNResponse():
   response = raw_input("Enter y or n: ")
   if response in ["y", "n"]:
     return response
   else:
     print("Invalid input.")
     return getYNResponse()

countLetter(s, l) - This function counts the occurences of the character l in the string s. countLetter('abracadabra', 'a') would return 5. When recursing on a string, the base case is often the empty list, "".

 def countLetter(s, l):
   if s == "":
     return 0
   elif s[0] == l:
     return 1 + countLetter(s[1:], l)
   else:
     return countLetter(s[1:], l)

reverse(s) - This function reverses a string, s. reverse('yellow') would return 'wolley'.

 def reverse(s):
   if len(s) <= 1:
     return s
   else:
     return reverse(s[1:]) + s[:1]

isPalindrome(s) - This function returns True if the string s is a palindrome (same backwards as forwards), False otherwise. isPalindrome('racecar') should return True. isPalindrome('palindrome') should return False.

 def isPalindrome(s):
   if len(s) <= 1:
     return True
   else:
     return s[0] == s[-1] and isPalindrome(s[1:-1])

isSorted(L) - Returns True if the list of ints L is in sorted order. Returns False otherwise.

 def isSorted(L):
   if len(L) <= 1:
     return True
   else:
     return L[0] < L[1] and isSorted(L[1:])

recLinearSearch(x, L) - A recursive version of linear search. Should return True if x is in L, False otherwise.

  def recLinearSearch(x, L):
    if len(L) == 0:
      return False
    else:
      if L[0] == x:
        return True
      else:
        return recLinearSearch(x, L[1:])

CS 21, Spring 2017

Recursion Practice - Answers