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², 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.