Recursion and anonymous functions are widely used in modern programming languages. But how does one write an function with no name that calls itself? The Y combinator is the answer to that question.
About a year and a half ago, I discovered a fantastic resource called Nathan’s University. Nathan was an instructor at one of the UC universities and this was basically his own self-produced MOOC. It was an online programming languages course that covered a whirlwind tour of several different languages, a guided path using a Parser Expression Generator to create a subset of scheme, how to create a type system and even a little bit about optimization.
Why bother? Why not just name the function?
It’s interesting to be able to implement recursion on anonymous functions, but the obvious question is “Why bother? Why not just name the function?” Personally, I do just name the functions. Especially in the case of the factorial function, I can’t see any benefit in using a Y combinator instead of just writing the function on its own in a straight-forward manner. I don’t have experience making any really large programs in scheme or similar languages, so I can’t speak to the possible advantages of this kind of structure when passing around a lot of higher order functions.
Combinators can handle memoization and more
There is something interesting in the case of the fibonacci function, though. By using a slightly different Y combinator-like function, it’s possible to do things like handle memoization inside the combinator! Below is an example that will cache the results of calculations of single function argument functions and use them instead each subsequent time they’re needed. It allows many naively written non-tail recursive functions, including the same fibonacci function from above to still perform well.
Why not just use once()?