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

---

This week we will have a gentle introduction to recursion, before next week's more intensive coverage.

All of this week's recursion problems must be solved without using lists, or any imports, or any arithmetic besides +,-,*,/,%.

For those who are interested in where we are headed, you may peek at a recent semester's recursion notes here. Note that we may make some small changes to those notes (for example, they are in Python2), but mostly we'll cover the same material.

---

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. isPrime(n) and nthPrime(n)
   
   def isPrime(n, factor=2): if (n < 2): return False elif (factor*factor > n): return True elif (n % factor == 0): return False else: return isPrime(n, factor+1) def nthPrime(n, guess=0, found=0): if (isPrime(guess)): found += 1 if (found == n+1): return guess else: return nthPrime(n, guess+1, found) assert([nthPrime(i) for i in range(10)] == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]) print("ok!")


6. 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, for fun:
   
   def vowelCount(s): # This is a bad idea, but showing that you can do this in one line... return 0 if (s=="") else int(s[0].upper() in "AEIOU") + vowelCount(s[1:]) assert(vowelCount("I am still reeeallly happy!!! :-)") == 8) print("ok!")

---