CMU 15-110: Principles of Computing
Recursion

1. Popular Recursion
2. General Recursive Form
3. Examples
   1. factorial
   2. power
   3. rangeSum
   4. listSum
   5. reverse
   6. digitCount
   7. vowelCount
   8. fibonacci
   9. towersOfHanoi
   10. kochSnowflakeFractal
4. Iteration vs Recursion Summary

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[0] 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[0] 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[0]) == 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").