title: Why will this recursive regex only match when a character repeats 2^n - 1 times?
body: <p>After reading <a href="https://stackoverflow.com/users/276101/polygenelubricants">polygenelubricants</a>'s series of articles on advanced regular expressions techniques (particularly <a href="https://stackoverflow.com/questions/3664881/how-does-this-java-regex-detect-palindromes">How does this Java regex detect palindromes?</a>), I decided to attempt to create my own PCRE regex to parse a palindrome, using recursion (in PHP).</p>
  
  <p>What I came up with was:</p>
  
  <pre><code>^(([a-z])(?1)\2|[a-z]?)$
  </code></pre>
  
  <p>My understanding of this expression is that it should either match zero or one characters (every string of less than 2 characters is implicitly a palindrome, as well as to account for palindromes with odd lengths in the recursion), or two of the same character separated by a recursion of the pattern.</p>
  
  <p>Unfortunately, it does not seem to be working that way, as you can see at <a href="http://www.ideone.com/a9T3F" rel="nofollow noreferrer">www.ideone.com/a9T3F</a>. Instead, only the strings of 2<sup>n</sup> - 1 (ie. empty string, <code>a</code>, <code>aaa</code>, <code>aaaaaaa</code>, <em>a</em><sup>15</sup>) repeated characters match the regular expression.</p>
  
  <p>Oddly, if I modify my pattern so that the recursion is optional (ie. <code>^(([a-z])(?1)?\2|[a-z]?)$</code>, see <a href="http://www.ideone.com/D6lJR" rel="nofollow noreferrer">www.ideone.com/D6lJR</a>, it only matches strings with a character repeated 2<sup>n</sup> times (ie. empty string, <code>a</code>, <code>aa</code>, <code>aaaa</code>, <code>aaaaaaaa</code>, <em>a</em><sup>16</sup>).</p>
  
  <p>Why is my regex not working the way I expect it to?</p>
  
  <p><strong>Note for the people who are itching to suggest not to use regex:</strong><br />The point of this question is to learn how to use recursive regular expressions properly. I know that this is not an effective way to determine if a string is a palindrome, and I wouldn't use a recursive regex if I for some reason had to determine palindromes in production code; I am just interested in learning more about the advanced aspects of regex.</p>