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₁, S₂, ... such that S = S₁ union S₂ union ... . The related notion of a partition of an integer, n, is a set of positive integers n₁, ..., 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²-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, v19, 1984.

Exercises

1. 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!
2. 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.
3. 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].
4. 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.
5. Write an iterative, non-recursive version of the following routine:

   procedure r(x)
      if p(x) then
         a(x)
      else
         b(x)
         r(f(x))
      end if
   end r
   

   where p is an arbitrary predicate, a and b are arbitrary procedures, and f is an arbitrary function.
6. 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.
7. 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.

   eg. n=4
   
         A          B          C
         |          |          |
        111         |          |
       22222        |          |
      3333333       |          |
     444444444      |          |
   ------------------------------------
   

   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.
   Hint: in the example above, discs 1 to 3 must be "parked" somewhere before disc 4 can be moved to peg C.
8. 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
   

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

   1 2 1 3 1 2 1 is irreducible over {1,2,3}
   

   but it cannot be extended because the following are not irreducible

   1 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
   

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