Left recursion

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (November 2015) (Learn how and when to remove this message)

In the formal language theory of computer science, left recursion is a special case of recursion where a string is recognized as part of a language by the fact that it decomposes into a string from that same language (on the left) and a suffix (on the right). For instance, ${\displaystyle 1+2+3}$ can be recognized as a sum because it can be broken into ${\displaystyle 1+2}$, also a sum, and ${\displaystyle {}+3}$, a suitable suffix.

In terms of context-free grammar, a nonterminal is left-recursive if the leftmost symbol in one of its productions is itself (in the case of direct left recursion) or can be made itself by some sequence of substitutions (in the case of indirect left recursion).