## Recursion

*Recursion* is where the definition of something makes use
of the thing being defined.
It is most often met in the recursive definition of
functions (methods, procedures, subroutines) and data-types but
recursive definitions of data-structures [All89, All93] are possible in a
suitable
programming language.
*Mutual recursion* is where the definitions of two or more things
make use of each other.

**Examples**:- 0! = 1 | n! = n*(n-1)!, n>0 —
*factorial function* **type**list e = nil | cons e (list e) —*data-type*- length nil = 0 | length cons h t = 1+length t
**type**tree e = emptyTree | fork (tree e) e (tree e)- height emptyTree = 0 |

height fork L elt R = 1+max (height L) (height R) - posInts = cons 1 (map succ posInts) —
*data structure*[1,2,3,...]

Commonly, recursion is effected by referring to the
*name* of the thing being defined but this is not essential,
an alternative being to use the
fixed-point operator Y,
see below.

### 1. Linear Recursion

#### 1.1. Procedures

Linear or unary recursion is where a definition makes one use of the thing being defined, as in the data-type 'list' and the function 'length' above. In general we have a procedure 'recP(.)'

proc recP(x) // a recursive procedure { if( isBC(x) ) BC(x); else { b(x); recP(f(x)); // recursion a(x); } }//recP(x)

where
'x' is one or more parameters,
BC(x) is the action to take for a *base case*,
isBC(x) recognises a base case,
b(x) is something that happens before the recursive call and
a(x) after, and f(x) acts on the parameter(s).

#### 1.2. Tail recursion

In the special case that a(.) is absent (or does nothing) we have

proc tailrP1(x) { if( isBC(x) ) BC(x); else { b(x); tailrP1(f(x)); } }//tailrP1(x)

which is *tail recursive* in that
the recursive call is the last thing that the procedure does;
such recursion can be replaced by a loop:

proc iterP1(x) // equivalent to tailrP1 { while( ! isBC(x) ) { b(x); x = f(x); } BC(x); }//iterP1(x)

When a(x) is present and f(x) has an inverse, f_inv(x), we can write

proc tailrP2(x) { var n = 0; proc fst(x) { if(isBC(x)) { BC(x); snd(n,f_inv(x)); } else { b(x); n ++ ; fst(f(x)); // tail rec } }//fst(x) proc snd(n, x) { if( n==0 ) return; else { a(x); snd(n-1, f_inv(x)); // tail rec } }//snd(n,x) fst(x); // begin }//tailrP2(x)

and fst(x) and snd(n.x) are both tail recursive and can be rewritten as loops:

proc iterP2(x) // equivalent to tailrP2 { var n = 0; while(!isBC(x)) { b(x); x = f(x); n ++ ; } // assert isBC(x) BC(x); while( n > 0 ) { x = f_inv(x); a(x); n -- ; } }//iterP2(x)

#### 1.3. Accumulating parameters

If f(x) does not have an inverse we have to collect,
in an *accumulating parameter*, xs, the various values that x goes
through so that b(.) can be applied to them in the reverse order to a(.).

proc tailrP3(x) { function fst(xs, x) // accumulate 'xs' { if( isBC(x) ) { BC(x); snd(xs.length-1, xs); } else { b(x); xs[xs.length] = x; // accumulate fst(xs, f(x)); // tail rec } }//fst(x) function snd(n, xs) // now use 'xs' { if( n < 0 ) return else { a(xs[n]); snd(n-1, xs); // tail rec } }//snd fst(new Array(), x); }//tailrP3(x)

now fst(.) and snd(.) are both tail recursive and so can be be rewritten as loops (exercise).

#### 1.4. Functions

A fairly general template for a recursive function (a subroutine that returns a value as its result) is

function recF(x) // linear recursive function { return isBC(x) ? FBC(x) : g(recF(f(x))); }

where FBC is what to do in the function's base case, f is called before recF is called recursively and g is called afterwards. If g is absent we have tail recursion

function tailrF1(x) { return isBC(x) ? FBC(x) : tailrF1(f(x)); }//tailrF1

which can be rewritten using iteration

function iterF1(x) { while( ! isBC(x) ) x = f(x); return FBC(x); }//iterF1(x)

When g is present we might write

function tailrF2(x) { function trF(gs,x) //trF is a tail rec fn { return isBC(x) ? gs(FBC(x)) : trF(function(z){return g(gs(z));}, f(x)); }//trF return trF(id, x); }//tailrF2(x)

where trF is tail recursive and its parameter, gs, accumulates the composition of an appropriate number of calls to g. This can be rewritten as two loops, one for trf and one for gs:

function iterF2(x) { var n = 0; while( ! isBC(x) ) { x = f(x); n ++ ; } x = FBC(x); for( ; n > 0; n -- ) x = g(x); return x; }//iterF2(x)

### 2. Binary Recursion

*Binary recursion* is where a definition can make two
recursive uses of the thing being defined,
for example, in the definition of the data-type of
binary trees, and
of many functions on those binary trees.
Some *divide and conquer* algorithms, such as merge sort and quick sort,
are naturally binary recursive.
Another example is generating sequences of n pairs of
matched brackets "by choices".

### 3. General Recursion

A more general form of recursion is where a definition can make any number of recursive uses of the thing being defined. One application of this is to get the effect of an arbitrary number of nested loops:

proc loops(m, n) { var state = new Array(); proc act(d) { if ( d==m ) { for(var i = 0; i<m; i ++) print(" "+state[i]); println("."); } else for(state[d]=0; state[d]<n; state[d]++) act(d+1); }//act(d) act(0); }//loops(m,n)

act(d) textually refers to act(d+1) just once but this is inside a loop.
By the time(s) that the *depth* d==m there are effectively that
many nested loops in operation.
(As it stands, loops(m,n) runs throgh all m-digit, base n+1, numerals.)
Many combinatorial constraint satisfaction problems (CSP)
(n-queens, Good sequences, ...)
can be solved with this kind of template by adding
appropriate tests to ensure that state[0..d) satisfies
the constraints of the particular problem.

### 4. Y

Lastly, the fixed-point operator, Y, provides a way to define a recursive function without the body of the function textually referring to itself.

function Y(G) { const Ggg = function(g) { return function(n) { return G(g(g))(n); }; }; return Ggg(Ggg); }//Y(G) function F(f) { return function(n) { return n<=1 ? 1 : n*f(n-1); }; }//F(f)

Y(F)(n) = n!.
Y(F) is a fixed-point of F, that is,
F(Y F) = Y F.
Note that
Ggg does not textually refer to itself
although it is applied to itself within Y,
nor does F textually refer to itself {f is not F) and, e.g.,
F(function(m){return m+1;})(n) = n^{2},
and F(factorial)(n) = factorial(n):

Y F n = Ggg(Ggg)(n)

where Ggg=function(g) {return function(n)
{return __F(g(g))(n)__;}}

= F(Ggg(Ggg))(n)

= n<=1 ? 1 : n*Ggg(Ggg)(n-1)

= n<=1 ? n! : n*(Y F (n-1)) — and induction...

= n!

The usual definition of Y in a
"lazy" functional
programming language is slightly different.

### 5. Tests

### References

- [All89] L. Allison, 'Circular Programs and Self-Referential Structures', Software Practice and Experience, 19(2), pp.99-109, doi:10.1002/spe.4380190202, 1989.
- [All93] L. Allison, 'Applications of Recursively Defined Data Structures', Australian Computer Journal, 25(1) pp.14-20, arxiv:2206.12795, 1993.