Good Math

Recursion: Y Oh Y Oh Y?

We’ve been building up the bits and pieces that turn λ calculus into a useful system. We’ve got numbers, Booleans, and choice operators. The only thing we’re lacking is some kind of repetition or iteration.

In λ calculus, all iteration is done by recursion. In fact, recursion is a pretty natural way of expressing iteration. It takes a bit of getting used to, but if you spend a lot of time in a functional language like Scheme, ML, or Haskell, you get used to it; and then when you return to an imperative language like Java, there’s a good chance that you’ll end up feeling frustrated about having to force all of your iterations into the loop structure instead of just being able to do them recursively!

It can be a bit ...