What is Open Recursion? (2013)

Here's a simple description. It's stripped down by removing the application, but gets to the heart of things.

---

Normally, you think of something as recursing by referencing its own name.

    sum(l) = if empty(l) then 0 else head(l) + sum(tail(l))

But it's worth noting that this is sort of a syntactic trick. We could also pass in the recursive bit as an argument.

    sumO(recur, l) = if empty(l) then 0 else head(l) + recur(tail(l))

The assumption here is that `recur` is essentially the same as calling `sum` again, but there's no particular reason this must be true. We could do something pathological with `sumO` if we like

    sumO(fn(x) { 0 }, [1,2,3]) ====> 1

we've short-circuited the recursion.

---

This is essentially the idea of open recursion: sumO is in an open recursive form. The goal here is to be able to intelligently change what the actual recursive call that gets passed in ends up being. Normally in OO languages this is used so that recursion defined in a superclass ends up executing using the definitions from the subclass, but there are other uses.

If you have a "mother recursive function" like the Y-combinator of fame then you can "close" open recursion

   sum = Y(sumO)

where

   Y(f) = f(Y(f))

So by this means all "closed" recursion arises via "open" recursion which is closed in a standard way.

Fhhhbnn