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