Computer Science 15-110, Fall 2009
Class Notes:  Getting Started with Recursion

In class today, we explored recursion (when a method directly or indirectly calls itself), with these examples:

• Recursion.java
  We wrote recursive gcd and then iterative and recursive versions of fib (nth Fibonacci number).  We saw that recursive fib was hopelessly slow, and we sped it up using memoization (see memoizedFib), which gave us the clarity of recursion with the speed of iteration!
   
• FloodFill.java
  We used recursion to do flood fill, which is basically when you pour a paintcan in a paint program and it fills the entire enclosed region.  We wrote that program (FloodFill.java) using EzGame, a simplified form of JComponentWithEvents (so you'll need EzGame.class in the same directory as your FloodFill.java file in order to compile and run it).
   
• Permutations.java
  We then used recursion to generate permutations -- all the ways you can select K objects from N total objects, where order matters (if order does not matter, then that would be combinations -- and this technique can be easily adapted to that case).
   
• Cryptarithms.java
  Finally, we extended our Permutations.java program with an interesting application -- solving cryptarithms.  For example, assign unique digits to the letters in the math phrase "SEND + MORE = MONEY" so that the arithmetic actually works (and there are no leading 0's).  This is really a permutation problem, since we'll solve it by trying every possible way to assign digits to these letters, and check each one in turn to see if the math works.  This simple and elegant solution is brought to you by recursion!!!!

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