CSE 320: Programming Languages @ CSU, San Bernardino

Go back to home page

Recursion

Required Reading

  1. Chapter 9 of PLAI. It is highly recommend to do the exercises in the book.

The focus in this reading should be on the following concepts:

  • What is a recursive data structure?
  • What is a cyclic data structure?
  • What does it mean for a computation to diverge?
  • Why does creating a cyclic datum require a box?
  • Why can't you write recursive functions without boxing?

Optional Reading

This reading is actually linked at the end of chapter 9 in PLAI!

  1. Daniel P. Friedman and Matthias Felleisen explaining how to get recursion without explicit state, in this chapter from their book The Little Schemer. Note that you will probably need to read this at least twice to understand what they're describing. This is some trippy stuff.

Advanced Reading

  1. “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” by Erik Meijer (major contributor to C♯, Haskell, lead developer of LINQ, one of the guys from the video on the first day of class), Maarten Fokkinga, and Ross Paterson.
  2. If the above is a bit much, try “An Introduction to Recursion Schemes” by Patrick Thomson, which summarizes the above paper in a more approachable way.