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