Recursion Patterns


We talked about recursion in Concepts of Programming Languages and I mentioned that Lecture 8 should more properly be entitled "Recursion Design Patterns." I think it would be interesting to write them up using the GoF templates. For reference, here are the patterns we discussed:

  • Simple recursion following the BNF
  • Mutual recursion following the BNF
  • Recursion using auxiliary variables
  • Recursion using an accumulator variable
  • Recursion over two variables following the BNF
  • Tail recursion (covered later)

These patterns provide a suite of tools for solving recursive problems. Remember to define constructors, selectors, and predicate functions to abstract any data type that isn't a straight list. This will make your programs cleaner and also keep you from making dumb mistakes. One other hint that I'm not sure I mentioned enough is to always pay attention to your return type and check your conditional arms to ensure they're all creating the right data type. This will help guide the recursion as well.

You should ensure that you've mastered each of these patterns and can identify when each should be applied. This will definitely be on the midterm.