Editing Left recursion (section)

{{Short description|Theory of computer sciences}}
{{technical|date=November 2015}}
In the [[formal language theory]] of [[computer science]], '''left recursion''' is a special case of [[recursion (computer science)|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, <math>1+2+3</math> can be recognized as a sum because it can be broken into <math>1+2</math>, also a sum, and <math>{}+3</math>, a suitable suffix.

In terms of [[context-free grammar]], a [[Terminal and nonterminal symbols#Nonterminal symbols|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).