Round 8: Recursion

Curry's Y combinator: Y = λf.(λx.f(xx))(λx.f(xx))

(Curry’s Y combinator.)

Learning objectives

In this round you will learn …

  • … that recursion is one of the basic programming principles to organize computations and data

  • … that the power of recursion stems from controlled self-reference that terminates at base cases

  • in essence, we can implement a large computation (or data structure)

    using smaller, self-similar, parts until the computation is so small so as to become trivial

  • … that many familiar mathematical objects and functions benefit from a recursive definition

  • for example, a string of length \(n\)

    either (i) is empty (when \(n=0\), the base case), or (ii) consists of a first character followed by a string of length \(n-1\) (when \(n\geq 1\), the recursive case)

  • recursive definitions lead to simple recursive functions that manipulate data or carry out a computation

  • recursive definitions admit mathematical analysis via mathematical induction (*)

  • … that recursion is naturally associated with a recursion tree that records all the stages of recursion

  • … that recursion is a natural tool to carry out exhaustive search

  • … how to use tail recursion to obtain efficiency

(Material that is marked with one or more asterisks (*) is good-to-know, but not critical to solving the exercises or passing the course.)