Recursion

This notebook will present recursion as something that we need to understand. It will serve as a motivation for several of the sections in the book.

Consider the following three function definitions:

\[\begin{split} \begin{array}{lcl} gcd(x,y) & = & \left\{ \begin{array}{ll} x & \mbox{if $y=0$} \\ \gcd(y, rem(x,y))) & \mbox{otherwise} \end{array} \right. \\ \\ A(x,y) & = & \left\{ \begin{array}{ll} y+1 &\mbox{if $x=0$} \\ A(x-1,1) & \mbox{if $x\neq 0$ and $y=0$}\\ A(x-1,A(x,y-1)) & \mbox{otherwise} \end{array} \right. \\ \\ collatz(n) & = & \left\{ \begin{array}{ll} 1 &\mbox{if $n \leq 1$} \\ 1 + collatz(n/2) & \mbox{if $n\geq 2$ is even } \\ 1 + collatz(3n) & \mbox{if $n\geq 3$ is odd} \end{array}\right. \end{array} \end{split}\]

In the first of these, \(rem(x,y)\) is the remainder when \(y\) is divided by \(x\).

In all three function definitions, the right-hand side includes calls to the same function which is being defined, but those calls are more complicated than what is allowed by primitive recursion. So from the form in which we have written them, it is not clear from first principles that any of these are computable in the first place.