Open recursion (Haskell)

There is a large class of problems that we can solve by nice mathematical recurrence relations. The recurrence is usually simple to read, to reason about, and describes the solution with concision. But a naive translation of this recurrence into code will very often lead to a very inefficient algorithm. When the sub-problems of the…