▼A Note on Recursion
On this page:
A Note on Recursion
2016-04-02
    contents  ← prev  up  next → 

A Note on Recursion

Éric Tanter

This note complements the chapter on recursion from PLAI (Chapters 9 and 10).

This note includes two parts. A semantic part, which discusses the necessity (or not) of defining a recursive binding construct like letrec (or rec in the language we implement), and an implementation part, which discusses tail recursion (and more generally, tail call) optimization.

    1 Expressiveness of the Lambda Calculus

      1.1 Non-terminating programs

      1.2 Recursion without a recursion construct

      1.3 The Y combinator

    2 Recursion: Efficiency Considerations

      2.1 Execution profiles

      2.2 Tail recursion and tail calls

      2.3 Making a function tail recursive

      2.4 Languages

      2.5 Trampoline

    contents  ← prev  up  next →