Recursion again

In mathematics and computer programming, a recursive definition is one that defines a process in terms of itself: a branch of a tree is a branch that ends in smaller branches. That’s recursive as the definition of a branch in this case refers to a definition of a branch.

A program that draws a branching tree recursively could go on for ever, or never get past its first branch, were it not that most recursive algorithms provide a stopping condition. Stop drawing branches when they get smaller than 5 centimetres.

Recursive grammars

The linguist Noam Chomsky noted that language grammars are recursive, e.g. a sentence is made up of a noun phrase followed by a verb phrase. In turn, a noun phrase begins with an optional adjectival phrase followed by a noun phrase. The definition of a noun phrase includes “noun phrase.” So it is recursive. A verb phrase has a similar recursive structure.

That simple formulation enables competent speakers of a language to construct and comprehend sentences ranging from the simple “The red ball bounced along the path” to the more complicated “The big red ball belonging to the little boy bounced along the concrete path in front of the neighbour’s house.” In keeping with a recursive grammar, the latter sentence contains several nested noun phrases and verb phrases.

It’s easy to see how recursion assumes special significance in theories of language and of mind, and of what it is to be human and creative. If language grammar is recursive then recursion contributes to human creativity. Thanks to recursive grammar structures, we are able instantly to invent, parse and make sense of new sentences that we’ve never thought of or heard before.

Though he doesn’t agree that there’s a nexus between recursion and creativity Chomsky attests to this commonly held inference from his own theories.

“a number of professional linguists have repeatedly confused what I refer to here as ‘the creative aspect of language use’ with the recursive property of generative grammars, a very different matter” (xiv).

I doubt, therefore I think

Consider Hofstadter and Dennett’s recursively-inspired propositions that we humans are self-aware, can see ourselves, are self reflexive and self-referential, basic elements of creativity and consciousness:

“Thus, ironically, something which we all have in common-the fact of being self-reflecting conscious beings-leads to the rich diversity in the ways we have of internalizing evidence about all sorts of things, and in the end winds up being one of the major forces in creating distinct individuals” (696).

At least, there’s something about being human in the idea of recursion. As precursor to this self reflexivity, René Descartes defined the solid foundation of his own existence in the self observation that he was capable of doubting his existence. That’s recursive.

“I never encountered any proposition so doubtful that I couldn’t get from it some fairly certain conclusion, even if it was only the conclusion that it contained nothing certain!” (13).

Hence: I doubt therefore I think; I think therefore I am.

Infinite semiosis

For some prominent thinkers, recursion also serves in unsettling certainties. Long before Chomsky, the pragmatic philosopher C.S. Peirce explored logic statements that had recursive structures. But he also wrote about meaning systems as infinitely recursive.

Peirce developed the concept of “infinite semiosis” whereby signs refer to other signs, which in turn refer to other signs ad infinitum, i.e. the paradoxical notion that signs chain together without ever seeming to alight firmly on a definitive object.

More recently, Jacques Derrida wrote about the way meaning resides in the traces left by a trail of interrelated signs, and the putative grounding of truth and meaning on an infinite chessboard or a configuration of inter-reflecting mirrors.

Derrida adopted Peirce’s concepts in arguing that the illusive object, the thing ultimately represented by the sign “functions only to give rise to an interpretant that itself becomes a sign and so on to infinity” (49).

Derrida examined in great detail and with many examples, how we depend on certainties, but paradoxically, these certainties are nothing of the kind. See posts tagged Derrida.


  • Chomsky, Noam. 2002. Syntactic Structures. Berlin: Mouton de Gruyter.
  • Chomsky, Noam. 2006. Language and Mind (3rd edition). Cambridge, UK: Cmabridge University Press.
  • Derrida, Jacques. 1976. Of Grammatology. Trans. Gayatri Chakravorty Spivak. Baltimore, Maryland: Johns Hopkins University Press
  • Descartes, René. 2017. Discourse on the Method of Rightly Conducting one’s Reason and Seeking Truth in the Sciences. Trans. Jonathan Bennett. Online translation.
  • Hofstadter, Douglas R., and Daniel C. Dennett. 1979. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Basic Books
  • Peirce, Charles Sanders. 1992. Some consequences of four incapacities. In Nathan Houser, and Christine Kloesel (eds.), The Essential Peirce, Selected Philosophical Writings Volume 1 (1867-1893): 28-55. Bloomington, IN: Indiana University Press.


  1. It’s a common mistake to confound infinite with unbounded. A process can continue without end and still be “bounded in a nutshell”. In particular, a sign process can pass from sign to interpretant sign to next interpretant sign ad infinitum without ever leaving a finite set of signs.

  2. The introduction of the question of meaning alters the nature of thought as certainty. From Descartes’ certainty of one’s thoughts, including doubt as a moment of thought, we move to peirce who in replacing idea with sign introduced uncertainty as part of the processual movement towards truth. For Peirce, meaning is never self evident. His notion of the ‘ideal interpretant’ problematises the idea of ‘infinite semiosis ‘ and distinguishes him in crucial ways from Derrida….

    1. No doubt. My idea in this short piece was simply to show in cursory fashion that Derrida drew on Peirce, whether or not he got Peirce right, and to show something of the legacies of the idea of recursion. I wrote this and the previous post to rehearse my contribution to an interesting conference called “Recursions: Music and Cybernetics” 24-25 October 2019, St Cecilia’s Hall, University of Edinburgh:

Leave a Comment

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.