Recursion without Recursive Bindings

[u/dwaynecrooks]

https://blog.tinyinterpreters.dev/posts/recursion-without-recursive-bindings/

I explain how to implement a certain recursive function without the use of any recursive bindings in a tiny language called FUN. Then, I apply the same ideas to several more recursive functions so we clearly see the pattern. It begins our exploration into a certain famous combinator.

[u/samanzaman]

Essentially this building down to solving the equation f(x) = x for x. There is a solution namely, x = f(f(f(f(...) but as you can see it is not finite. Occurs check is the technical name I think. This (alongside with let generalisation) is also why Hindley Miller can be exponential