CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion (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. fib(n)
   
   def fib(n): if (n < 2): return 1 else: return fib(n-1) + fib(n-2) assert([fib(n) for n in range(10)] == [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]) print("ok!")


3. gcd(x, y)
   
   def gcd(x, y): if (y == 0): return x else: return gcd(y, x%y) assert(gcd(2**5 * 3**4 * 5**2, 2**3 * 3**8 * 7) == (2**3 * 3**4)) print("ok!")


4. factorial(n)
   
   def factorial(n): if (n == 0): return 1 else: return n * factorial(n-1) assert(factorial(5) == 5*4*3*2*1) print("ok!")


5. 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!")


6. 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!)

   ---