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

1. digitSum(n)   video
   

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

   Select Visualize Run


2. fib(n)   video
   

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

   Select Visualize Run


3. gcd(x, y)   video
   

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

   Select Visualize Run


4. factorial(n)   video
   

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

   Select Visualize Run


5. vowelCount(s)   video
   

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

   Select Visualize Run
   
   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!")

   Select Visualize Run


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

      Select Visualize Run
   
   
   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!)

      Select Visualize Run
   
   
   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

      Select Visualize Run
   
   
   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!)

      Select Visualize Run

   ---