5 Recursion

5.1 See Section 5

Sorry, couldn't resist.

5.2 A Brief History

In functional languages, recursion plays an important role. For Erlang in particular, recursion is important because variables can't be changed. It is therefor often very useful to take advantage of recursion in order to work with changing values (examples are given in the latter half of this chapter).

However, recursion is interesting in and of itself. The roots of functional programming languages such as Lisp, ML, Erlang, Haskell and others, can be traced to the concept of recursion in general and the λ-calculus in particular.

The Italian mathematician Giuseppe Peano seems to have been one of the first to have made prominent use of recursion when defining his axioms for the natural numbers. Furthermore, Peano gave Bertrand Russell a copy of his "Formulario" (in fact, he gave Russell all of his published works!). This impacted Russell hugely and quite possibly influenced his work on the "Principia Mathematica" which he coauthored several years later.

It was from the Principia that Alonzo Church derived his lambda notation. When Church's student, John McCarthy, created Lisp, he used both the lambda notation and the related concept of recursion in his new language. (Interestingly enough, McCarthy and Dijkstra both advocated for the inclusions of recursion in ALGOL.) From John McCarthy's work onward, the lambda and recursion have been our constant companions.

5.3 A Preview

In the sections of the user guide, we explore various aspects of recursion as they can be formulated in Lisp Flavored Erlang. We will cover the following:

  • The Dedekind-Peano Axioms
  • Primitive Recursive Functions
  • Total Recursive Functions
  • The λ-Calculus
  • Practical Examples in Computing
  • Tail-Calls

If you just want to jump to the practical examples, please do so! You should feel no guilt when enjoying LFE or reading about LFE :-) The other sections are provided simply because it is very rare to find a practical coverage of the foundations of recursion and the λ-Calculus. There may be readers out there who want to know this reasons and history behind the concepts studied; most of this chapter is for them.