Recursion has never been invented: A tale of intrigue

In the cold December of 1959, E.W. Dijkstra — one of the greatest computer scientists of all time — made his first international phone call. In it, he tricked the editor of the Algol 60 committee to explicitly introduce recursion in a programming language for the first time.

This phone call was never necessary: recursion has never been invented, it has been discovered. In this talk, we'll explain why...

We'll not only explore the very concept of recursion and its mathematical origins but also show how we can implement it without any explicit support, live-coding together we'll reinvent one of the most beautiful ideas in computer science: the Y combinator. (This was a great source of curiosity and Lucas was asked many questions about it after his talk at HolyJS 2018 Moscow where he mentioned it.)

To keep it hardcore we'll explore how our engines deal with recursion, talk about the call stack, and demystify concepts such as proper tail calls, tail call optimisation, syntactic tail calls and shadow stacks. Finally, we will see what is the current state of recursion-related features and support in the JS ecosystem and where we're going to.

If simplicity is the ultimate sophistication, then recursion is the best example of elegance... once you understand it properly.