# CMU 15-110: Principles of Computing Recursion

1. Popular Recursion
1. Google search: Recursion
2. Matryoshka Dolls: See the Wikipedia page and this Google image search
3. Droste Effect: See the Wikipedia page and this Google image search
4. Fractals: See the Wikipedia page and this Google image search and this infinitely-zooming video
5. The Chicken and Egg Problem (mutual recursion)
6. Sourdough Recipe: First, start with some sourdough, then...
7. Wikipedia page on Recursion: See here.

2. General Recursive Form
def recursiveFunction(): if (this is the base case): # no recursion allowed here! do something non-recursive else: # this is the recursive case! do something recursive

3. Examples

1. factorial
def factorial(n): # assume n is a non-negative integer if (n == 0): return 1 else: return n * factorial(n-1) print(factorial(5)) # 120 (5*4*3*2*1)

2. power
def power(base, expt): # assume expt is non-negative integer if (expt == 0): return 1 else: return base * power(base, expt-1) print(power(2,5)) # 32

3. rangeSum
def rangeSum(lo, hi): if (lo > hi): return 0 else: return lo + rangeSum(lo+1, hi) print(rangeSum(3,5)) # 12 (3+4+5)

4. listSum
def listSum(L): if (L == [ ]): return 0 else: first = L rest = L[1:] return first + listSum(rest) print(listSum([2,3,5,7])) # 17

5. reverse
def reverse(L): # assume L is a 1d list if (L == [ ]): return [ ] else: first = L rest = L[1:] return reverse(rest) + [first] print(reverse([1,2,3])) # [3,2,1]

6. digitCount
def digitCount(n): if (n < 10): return 1 else: return 1 + digitCount(n//10) print(digitCount(13142)) # 5

7. vowelCount
def vowelCount(s): if (s == ''): return 0 elif (isVowel(s) == True): return 1 + vowelCount(s[1:]) else: return vowelCount(s[1:]) def isVowel(c): return c in 'AEIOUaeiou' print(vowelCount("Isn't this amazing?")) # 5 (Iiaai)

8. fibonacci
def fib(n): if (n < 2): return 1 else: return fib(n-1) + fib(n-2) print([fib(n) for n in range(15)])

9. towersOfHanoi
def move(n, source, target, temp): if (n == 1): print((source, target), end="") else: move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) def hanoi(n): print("Solving Towers of Hanoi with n =", n) move(n, 0, 1, 2) print() hanoi(4)

10. kochSnowflakeFractal
Python code: koch-snowflake.py
Key excerpt:
def kochSide(length, n): if (n == 1): turtle.forward(length) else: kochSide(length/3.0, n-1) turtle.left(60) kochSide(length/3.0, n-1) turtle.right(120) kochSide(length/3.0, n-1) turtle.left(60) kochSide(length/3.0, n-1)

4. Iteration vs Recursion Summary
 Recursion Iteration Elegance Performance Debuggability

Note: These are general guidelines. For example, it is possible to use recursion with high performance, and it is certainly possible to use (or abuse) iteration with very low performance.

Conclusion (for now): Use iteration when practicable. Use recursion when required (for "naturally recursive problems").