CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion Examples (Getting Started)

1. digitSum(n)
   
   def digitSum(n): if (n < 0): return digitSum(abs(n)) elif (n < 10): return n else: return (n%10) + digitSum(n//10) assert(digitSum(-12345) == 1+2+3+4+5) print("ok!")


2. vowelCount(s)
   
   def vowelCount(s): if (s == ""): return 0 else: thisCount = 1 if (s[0].upper() in "AEIOU") else 0 restCount = vowelCount(s[1:]) return thisCount + restCount assert(vowelCount("I am reeeallly happy!!! :-)") == 7) print("ok!")
   
   Once again, dividing in halves:
   
   def vowelCount(s): if (s == ""): return 0 elif (len(s) == 1): return 1 if (s[0].upper() in "AEIOU") else 0 else: mid = len(s)//2 return vowelCount(s[:mid]) + vowelCount(s[mid:]) assert(vowelCount("I am reeeallly happy!!! :-)") == 7) print("ok!")


3. Base Case Blues
   1. The problem:
      
      def vowelCount(s): # same as above... if (s == ""): return 0 else: thisCount = 1 if (s[0].upper() in "AEIOU") else 0 restCount = vowelCount(s[1:]) return thisCount + restCount s = "This works!" print(vowelCount(s)) # 2 L = list(s) print(vowelCount(L)) # crash! IndexError: list index out of range
   
   
   2. The solution:
      
      def vowelCount(s): # notice the change... if (len(s) == 0): return 0 else: thisCount = 1 if (s[0].upper() in "AEIOU") else 0 restCount = vowelCount(s[1:]) return thisCount + restCount s = "This works!" print(vowelCount(s)) # 2 L = list(s) print(vowelCount(L)) # 2 (now lists work, too!)
   
   
   3. The problem (once again):
      
      def mySum(L): # duplicating built-in sum function recursively, but with a problem... if (L == [ ]): return 0 else: return L[0] + mySum(L[1:]) print(mySum([0,1,2,3])) # 6 (this works) print(mySum(range(4))) # crash! IndexError: range object index out of range
   
   
   4. The solution:
      
      def mySum(L): # duplicating built-in sum function recursively, now fixed... if (len(L) == 0): return 0 else: return L[0] + mySum(L[1:]) print(mySum([0,1,2,3])) # 6 (this works) print(mySum(range(4))) # 6 (this works, too!)

   ---