## Recursion

*Recursion*
occurs where the definition of an entity refers to the entity itself.
Recursion can be *direct* when an entity refers to itself directly
or *indirect* when it refers to other entities which refer to it.
A (directly) recursive routine calls itself.
*Mutually recursive* routines are an example of indirect recursion.
A (directly) recursive data type contains pointers
to instances of the data type.

Recursive routines are often simple and elegant and their correctness easily seen. This is particularly true of routines over recursive data types where the structure of a routine follows that of the type. Many mathematical functions are defined recursively and their translation into a programming language is often trivially easy. Recursion is natural in Ada, Algol, C, C++, Haskell, Java, Lisp, ML, Modula, Pascal, Turing and a great many other programming languages.

Used carelessly, recursion *can* sometimes
result in an inefficient routine.
However there is no necessity for a recursive routine
to be less efficient than a non-recursive one.

## Linear Recursion

The simplest form of recursion is *linear recursion*.
It occurs where an action has a simple repetitive structure
consisting of some basic step followed by the action again.

See the [Linear recursion page].

## Mutual Recursion.

In order to check and compile a routine call,
a compiler must know the type of the routine,
the number of parameters and so on.
In direct recursion the routine header
which contains this information is seen before any call
within the procedure body or later.
In mutual recursion the routines must be defined in some order.
This means that a call of at least one routine must be compiled before
its definition is seen.
Different programming languages approach this problem in various ways.
Some use separate **forward** definitions of routine headers
to give sufficient information to compile a call
and **body** definitions to contain those calls.

See the section on parse-trees for useful examples of mutual recursion.

## Binary Recursion

A *binary-recursive* routine (potentially) calls itself twice.

See the [Binary recursion page].

### Edit-Distance Revisited.

An earlier section described the dynamic programming algorithm (DPA)
which calculates the
edit-distance
of two strings s1 and s2.
This algorithm takes O(|s1|*|s2|) time and space.
Hirschberg (CACM **18**(6) 341-343 1975)
showed that an optimal alignment can
be recovered in O(|s1|*|s2|) time and only O(|s2|) space
using binary-recursion.

See the [O(|s2|)-space page].

## N-ary Recursion & Permutations

The most general form of recursion is *n-ary recursion*
where n is not a constant but some parameter of a routine.
Routines of this kind are useful in generating
combinatorial objects such as permutations.

See the [Permutation page].

### Partitions

A *partition* of a set, S,
is a collection of *disjoint* sets
S_{1}, S_{2}, ...
such that
S = S_{1} union S_{2} union ... .
The related notion of a partition of an integer, n,
is a set of positive integers n_{1}, ..., n_{m},
that add up to n.

See the [Partition page].

### N-Queens

The n-queens problem is a classic combinatorial problem. It is required to place n queens on an n*n chess board so that no two queens threaten each other. Therefore no two queens can be on the same row, column or diagonal. There must be a queen on each column and all their row numbers must differ so a solution can be represented as a permutation of the rows.

See the
[N-Queens page] and also the
[3-D N^{2}-Queens]
problem.

## Notes

There are many books on the topic of recursion, e.g.

- J. S. Rohl.
*Recursion via Pascal*, C.U.P. Cambridge Computer Science Texts, v**19**, 1984.

## Exercises

- Identify more linear-recursive songs.
Are there any binary-recursive songs or stories?

See 'The Telnet Song', Comm. A.C.M.**27**(4) 347-348 April 1984, words and music by `The Great Quux'. Write a program to print n verses and choruses of this song. Keep n small! - The term
*ancestor*is recursive: A parent is an ancestor and an ancestor of a parent is an ancestor. Give some other recursive terms in everyday use. - For light-hearted discussion:
- Grelling's paradox:
A word is
*autological*if it applies to itself. Short is autological. A word is*heterological*if it does not apply to itself. Long is heterological. Is autological autological? Is heterological heterological?

- W. V. O. Quine: "Yields a falsehood when appended to its own quotation" yields a falsehood when appended to its own quotation.
- See [self-referential sentences].

- Grelling's paradox:
A word is
- Run tests to determine if it is faster on your system to use the exponentiation algorithm Expn(x,n) or the operator x**n, if it is provided, for various values of x and n.
- Write an iterative, non-recursive version of the following routine:

where p is an arbitrary predicate, a and b are arbitrary procedures, and f is an arbitrary function.procedure r(x) if p(x) then a(x) else b(x) r(f(x)) end if end r

- Write a recursive routine to print an integer in any base b, -16<=b<=16 and b~=0. The letters A..F are used for the "digits" 10..15.
- The
*Towers of Hanoi*is an old puzzle. It consists of 3 pegs, A, B and C, and n discs of different sizes. Each disc has a hole in its centre. Initially all discs are on peg A and in order of decreasing size. The object is to move all discs to peg number C.

The only legal move is to transfer a single (top-most) disc from one peg to another peg. At no time may a larger disc sit on top of a smaller disc. Write a binary-recursive routine to print a sequence of moves to solve the puzzle.eg. n=4 A B C | | | 111 | | 22222 | | 3333333 | | 444444444 | | ------------------------------------

Hint: in the example above, discs 1 to 3 must be "parked" somewhere before disc 4 can be moved to peg C. - A
*partition*of a positive integer n is a sequence of positive integers that sum to n. Write a program to print all non-increasing partitions of n.eg. n=4 4 3 1 2 2 2 1 1 1 1 1 1

- Axel Thue (1906) defined the idea of an
*irreducible sequence*. A sequence is irreducible if it contains no adjacent repeated substring. For example

but it cannot be extended because the following are not irreducible1 2 1 3 1 2 1 is irreducible over {1,2,3}

However, there are irreducible sequences of1 2 1 3 1 2 1 1 -- 1 repeated 1 2 1 3 1 2 1 2 -- 1 2 repeated 1 2 1 3 1 2 1 3 -- 1 2 1 3 repeated

*every*possible length. Write a program to print all irreducible sequences of length `n' over the elements {1,2,3}.