The Beauty of Recursion- 2 mins
Recursion is one of the most fascinating and elegant concepts in Computer Science. The feeling of figuring out recursive algorithms & data structures is a special one for a software developer. In this context, there is probably no better source than The Little Schemer book for both understanding and satisfying your recursive appetite.
Although this might seen like just a book about Scheme, I’d say this is mostly a book about thinking recursively. Based entirely on questions, puzzles, and exercises which guide you gradually from the most basic concepts, like atoms and s-expressions, to the most mind-blowing ones, like the Y Combinator, the teaching method is quite engaging and very unusual when compared to traditional programming books.
The Little Schemer seems to be a popular book among Clojure developers like my friend Marcos. Even though there are idiomatic differences to Scheme, it is totally possible to implement all the exercises in the book using Clojure. Here is my test-driven version: github.com/vvgomes/little-schemer
The Y Combinator
By far, the most difficult challenge in the book is the Y Combinator. In summary, the goal is to describe recursion formally using Lambda Calculus theory, which in practice means pretty much defining recursive functions with anonymous functions only. In the example given in the book we move from a traditional recursive function definition like this: