Left recursion

<p>In the <a href="/facts/Formal_language_theory/crDTyP8q">formal language theory</a> of <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, left recursion is a special case of <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursion</a> 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, 
  
    
      
        1
        +
        2
        +
        3
      
    
    {\displaystyle 1+2+3}
  
 can be recognized as a sum because it can be broken into 
  
    
      
        1
        +
        2
      
    
    {\displaystyle 1+2}
  
, also a sum, and

+
        3
      
    
    {\displaystyle {}+3}
  
, a suitable suffix.
</p><p>In terms of <a href="/facts/Context-free_grammar/yu1FFdK4">context-free grammar</a>, a <a href="/facts/Terminal_and_nonterminal_symbols/3BLz2wJU">nonterminal</a> 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).
</p>

Left recursion open-in-new

Left recursion