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 last semester's recursion notes here. Note that we may make some small changes to those notes, but mostly we'll cover the same material.

---

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)

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])

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

def factorial(n):
    if (n == 0): return 1
    else: return n * factorial(n-1)

assert(factorial(5) == 5*4*3*2*1)

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])

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)

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)