# 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!)