What is recursion?

A definition

The linguistic term recursion has been adopted from mathematics and computer sciences, where it stands for the act of defining an object in terms of that object itself—in short: a definition that uses itself as part of itself.¹ As a notion used in some schools of linguistics, it is used to refer to a set of phrase structure rules that allows a category to embed a category of the same type. There are structural definitions of recursion, based on phrase structure geometry, and computational definitions, based on processing mechanisms that assign structures (Dougherty 2004).

In its most general form, recursion can be said to be present when some constituent occurs within another constituent of the same type. For instance, a noun phrase can appear within another noun phrase (John’s wife, or the book on the table) or a clause within another clause (Jane is the woman that John loves). It can be represented with a rule like (1a), which contains the same symbol on both sides of the arrow and thereby produces an environment for its own reapplication.

Following other linguistic treatments, we will be concerned primarily with only one type of recursion—one that is widely held to be the prototypical one, which we refer to as embedding recursion and, unless otherwise stated, we will henceforth use ‘‘recursion’’ as a shorthand for embedding recursion (see “Embedding, iteration, and succession”). This type can be described thus: [A [B]] is a construction that—in some sense—is structurally derived from another construction [A] which is of the same type, where B is embedded in A, cf. (1b). Recursion can but need not be productive, in that the output (to the right of the arrow) can form the input of another application of the same rule, as in (1c).

Recursion is not a property of language but rather the product of a given theory designed to describe or account for language structure;² given an appropriate theory, one might argue that language is no more recursive than, say, biological reproduction, or some other natural phenomenon. Accordingly, when using this term we are not maintaining that language, or language structure, has recursion but rather that there are certain properties to be observed in language that can appropriately be described in terms of a construct of the form proposed in (1); as we will see below (“Treatment of recursion in linguistic description”), there are theories that do without ‘‘recursion.’’

We are restricted to what may be called direct recursion to distinguish it from other kinds of recursion, such as indirect recursion, where there is not one recursive rule but a recursive ‘‘loop’’, in that two (or more) rules jointly produce recursion, as in the set of rules of (2).³ Indirect recursion raises a number of issues that would be beyond the scope of the present treatment; hence, we will have nothing to say about it and its implications for language evolution.

Embedding recursion (1b) entails hierarchy, or phrase structure—be that conceptual or syntactic hierarchy; but not all hierarchy or phrase structure is necessarily recursive: Instances of hierarchy are only recursive when they are in accordance with (1b), that is when the same category occurs both to the left and to the right of the arrow. In dealing with embedding recursion, a number of additional distinctions have been made (see Chomsky 1957; Christiansen and Chater 1999). First, there is a basic distinction between tail and nested (or center-embedded) recursion. In linguistics, tail recursion involves embedding at the edge of a phrase, or invokes another instance of itself as a final step, while nested recursion (or ‘‘true’’ recursion) involves embedding in the center, leaving material on both sides of the embedded component. Second, there is a distinction between counting and mirror recursion. In order to parse strings from left to right it is necessary to count the number of As and note whether it equals the number of Bs, as, for example, in AAABBB. Counting recursion corresponds to sentence constructions such as ‘‘if S1, then S2’’ and ‘‘either S1, or S2’’, which can be nested arbitrarily deeply, for example, ‘‘if if if S1, then S2, then S3, then S4’’. In mirror recursion (which corresponds to center embedding), the first A is matched with the last A: A[BB]A, as in the English example The boy girls like ran away. And crossed embedding (identity recursion, cross-dependency) involves dependencies where A–A are crossed by B–B, that is {A [A B} B].

¹ In mathematics, it is used for example for an expression each term of which is determined by application of a formula to preceding terms, or an expression such that each term is generated by repeating a particular mathematical operation.

² Fritz Newmeyer (p.c.) rightly draws attention to the fact that this applies not only to recursion but to most constructs in linguistics.

³ In some traditions of generative grammar, a common kind of indirect recursion is found in the following set of rules (where there is an intervening generating operation): S → NP VP; VP → V(S).

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الفكرية يقيم أمسيات قرآنية في غانا ونيجيريا ضمن برنامج سفرة الكفيل الرمضانية

شعبة التوجيه الديني النسوي تختتم محافلها القرآنية الرمضانية

المجمع العلمي يختتم مسابقة رحيق الولاء ضمن فعاليات ملتقى النورين الخامس في بابل

الحلقة 27 من جائزة العميد القرآنية تشهد مشاركة 5 قرّاء من فئة الكبار ضمن المرحلة النهائية

المزيد

الآخبار الصحية

كوب قبل النوم.. مشروب طبيعي يحارب الأرق

دون أدوية.. طريقة طبيعية لخفض ضغط الدم بفعالية مذهلة

المعكرونة ليست عدوك.. كيف تصبح جزءا من وجبة صحية متوازنة؟

دراسة: تناول القهوة يوميا يخفض خطر الإصابة بالاضطرابات النفسية

المزيد

الآخبار التكنلوجية

علماء روس يخططون لبناء منشأة للكشف عن المادة المظلمة

ثاني أكسيد الكربون ليس تهديدا للمناخ فقط.. بل لصحة الإنسان أيضا!

ديدان الأرض تكشف تلوث التربة بالمعادن الثقيلة

خبير أرصاد جوية: ظاهرة النينيو القادمة قد تكون الأقوى خلال 10 سنوات

المزيد

مواضيع ذات صلة

Are there languages without recursion?

Treatment of recursion in linguistic description

Embedding, iteration, and succession

Simple vs. productive recursion

Manifestations

What is recursion?

On the rise of recursion

Case study: be going to

The subjectification approach

Case study: the evolution of must

Invited Inferencing Theory

Case study: SPACE-TO-POSSESSION