Recursion

This picture of a so-called Julia fractal  shows something we also find as one of the most important properties of natural language. Let us say the red figure in the center is a flower with eight petals. It is embedded  in successive 8-petal flower patterns of the same kind. Embedding of a pattern in a pattern of the same kind is what mathematicians call recursion.

The set of natural numbers {1, 2, 3,..., etc.} is defined recursively in the following way:

1 = [ 1 ]

2 = [ [ 1 ]  +  1 ]

3 = [ [ [ 1 ]  + 1 ]  +  1 ]

etc.

As in the picture above,  each successive structure may be embedded in a bigger structure of the same type, namely a structure consisting of the previous structure + 1.

Recursion is one of the most fundamental properties of the grammars of natural languages. For instance, each sentence can be embedded in a bigger sentence with similar structure:

(1)    [he dreams]

(2)    he dreams  that [ he dreams]

(3)    he dreams  that [ he dreams that [ he dreams ] ]

etc.

Each sentence can be expanded by making it part of a bigger sentence that begins with he dreams that.  Like counting, we can go on with this step for ever. Of course, we almost never use such sentences with the same words, but the recursion is not so much about the words but about structures and types of words. The following example sounds a lot more normal and is based on the same type of recursion as found in (3):

(4)    I  think that he knows that he dreams

In any case, there is no biggest  natural number and there is no longest sentence. Both counting and sentence construction show the same kind of infinity based on recursion. The possession of recursive grammars is typical of the human mind and by no means a necessary property of communication systems. Chimpanzees can to some extent learn to communicate with unstructured symbols and deal with limited quantities. However, their brain is not capable of recursion: they can be taught neither to count nor to expand series of symbols in a recursive way. It is not generally known, but more than anything else, it is recursion that makes us human!

(Picture  (c) 1995:  Hans Lauwerier, Symmetrie, Kunst en Computers. Aramith, Haarlem, 1995)