Computer Science 15-110, Spring 2011
Class Notes:  Recursion Part 1

1. General Recursive Form
2. Basic Examples
1. rangeSum
2. listSum
3. power
4. interleave
   
3. Examples with Multiple Base or Recursive Cases
1. power with negative exponents
2. interleave with different-length lists
   
4. Examples with Multiple Recursive Calls
1. fibonacci
2. towersOfHanoi
5. Examples Comparing Iteration and Recursion
   
1. factorial
2. reverse
3. gcd
6. Iteration vs Recursion Summary

Recursion Part 1

1. 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
   
   See http://en.wikipedia.org/wiki/Recursion_(computer_science)
   
   
2. Basic Examples
   
   
1. rangeSum
   
   def rangeSum(lo, hi):
       if (lo > hi):
           return 0
       else:
           return lo + rangeSum(lo+1, hi)
   
   print rangeSum(10,15) # 75
   
   
2. listSum
   
   def listSum(list):
       if (len(list) == 0):
           return 0
       else:
           return list[0] + listSum(list[1:])
   
   print listSum([2,3,5,7,11]) # 28
   
   
3. 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
   
   
4. interleave
   
   def interleave(list1, list2):
       # assume list1 and list2 are same-length lists
       if (len(list1) == 0):
           return []
       else:
           return [list1[0] , list2[0]] + interleave(list1[1:], list2[1:])
   
   print interleave([1,2,3],[4,5,6])
   
   
3. Examples with Multiple Base or Recursive Cases
   
   
1. power with negative exponents
   
   def power(base, expt):
       # This version allows for negative exponents
       # It still assumes that expt is an integer, however.
       if (expt == 0):
           return 1
       elif (expt < 0):
           return 1.0/power(base,abs(expt))
       else:
           return base * power(base, expt-1)
   
   print power(2,5) # 32
   print power(2,-5) # 1/32 = 0.03125
   
   
2. interleave with different-length lists
   
   def interleave(list1, list2):
       # This version allows for different-length lists
       if (len(list1) == 0):
           return list2
       elif (len(list2) == 0):
           return list1
       else:
           return [list1[0] , list2[0]] + interleave(list1[1:], list2[1:])
   
   print interleave([1,2,3],[4,5,6,7,8])
   
   
4. Examples with Multiple Recursive Calls
   
   
1. fibonacci
   
   A)  First attempt
   
   # Note: as written, this function is very inefficient!
   # (We need to use "memoization" to speed it up, which we'll learn later!)
   def fib(n):
       if (n < 2):
           # Base case:  fib(0) and fib(1) are both 1
           return 1
       else:
           # Recursive case:  fib(n) = fib(n-1) + fib(n-2)
           return fib(n-1) + fib(n-2)
   
   for n in range(15): print fib(n),
   
   B) Once again, printing call stack using recursion depth:
   
   def fib(n, depth=0):
       print "   "*depth, "fib(", n, " )"
       if (n < 2):
           # Base case:  fib(0) and fib(1) are both 1
           return 1
       else:
           return fib(n-1, depth+1) + fib(n-2, depth+1)
   
   fib(4)
   
   C) Even better (printing result, too):
   
   def fib(n, depth=0):
       print "   "*depth, "fib(", n, " )"
       if (n < 2):
           result = 1
           # Base case:  fib(0) and fib(1) are both 1
           print "   "*depth, "-->", result
           return result
       else:
           result = fib(n-1, depth+1) + fib(n-2, depth+1)
           print "   "*depth, "-->", result
           return result
   
   fib(4)
   
   D) Finally, not duplicating code:
   
   def fib(n, depth=0):
       print "   "*depth, "fib(", n, " )"
       if (n < 2):
           result = 1
       else:
           result = fib(n-1, depth+1) + fib(n-2, depth+1)
       print "   "*depth, "-->", result
       return result
   
   fib(4)
   
   
2. towersOfHanoi
   
   A)  First attempt (without Python)
   
   # This is the plan we generated in class to solve Towers of Hanoi:
   magically move(n-1, frm, via, to)
             move(  1, frm, to,  via)
   magically move(n-1, via, to,  frm)
   
   B)  Turn into Python (The "magic" is recursion!)
   
   def move(n, frm, to, via):
       move(n-1, frm, via, to)
       move(  1, frm, to,  via)
       move(n-1, via, to,  frm)
   
   move(2, 0, 1, 2)  # Does not work -- infinite recursion
   
   C)  Once again, with a base case
   
   def move(n, frm, to, via):
       if (n == 1):
           print (frm, to),
       else:
           move(n-1, frm, via, to)
           move(  1, frm, to,  via)
           move(n-1, via, to,  frm)
   
   move(2, 0, 1, 2)
   
   D)  Once more, with a nice wrapper:
   
   def move(n, frm, to, via):
       if (n == 1):
           print (frm, to),
       else:
           move(n-1, frm, via, to)
           move(  1, frm, to,  via)
           move(n-1, via, to,  frm)
   
   def hanoi(n):
       print "Solving Towers of Hanoi with n =",n
       move(n, 0, 1, 2)
       print
   
   hanoi(4)
   
   E)  And again, printing call stack and recursion depth:
   
   def move(n, frm, to, via, depth=0):
       print (" " * 3 * depth), "move", n, "from", frm, "to", to, "via", via
       if (n == 1):
           print (" " * 3 * depth), (frm, to)
       else:
           move(n-1, frm, via, to, depth+1)
           move(1, frm, to, via, depth+1)
           move(n-1, via, to, frm, depth+1)
   
   def hanoi(n):
       print "Solving Towers of Hanoi with n =",n
       move(n, 0, 1, 2)
       print
   
   hanoi(4)
   
   
5. Examples Comparing Iteration and Recursion
   
   

   Function	Iterative Solution	Recursive Solution	Recursive Solution with Stack Trace
   factorial	def factorial(n):     factorial = 1     for i in range(2,n+1):         factorial *= i     return factorial print factorial(5)	def factorial(n):     if (n < 2):         return 1     else:         return n*factorial(n-1) print factorial(5)	def factorial(n, depth=0):     print "   "*depth, "factorial(",n,"):"     if (n < 2):         result = 1     else:         result = n*factorial(n-1,depth+1)     print "   "*depth, "-->", result     return result print factorial(5)
   reverse	def reverse(s):     reverse = ""     for ch in s:         reverse = ch + reverse     return reverse print reverse("abcd")	def reverse(s):     if (s == ""):         return ""     else:         return reverse(s[1:]) + s[0] print reverse("abcd")	def reverse(s, depth=0):     print "   "*depth, "reverse(",s,"):"     if (s == ""):         result = ""     else:         result = reverse(s[1:], depth+1) + s[0]     print "   "*depth, "-->", result     return result print reverse("abcd")
   gcd	def gcd(x,y):     while (y > 0):         oldX = x         x = y         y = oldX % y     return x print gcd(500, 420) # 20	def gcd(x,y):     if (y == 0):         return x     else:         return gcd(y,x%y) print gcd(500, 420) # 20	def gcd(x,y,depth=0):     print "   "*depth, "gcd(",x, ",", y, "):"     if (y == 0):         result = x     else:         result = gcd(y,x%y,depth+1)     print "   "*depth, "-->", result     return result print gcd(500, 420) # 20



6. 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 (ab)use iteration with very low performance.
   
   Conclusion (for now):  Use iteration when practicable.  Use recursion when required (for naturally recursive problems).
   

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem