When you replied, my first thought—and rightly so, I think—was “Oh no, I've under-specified the problem again”, and I'm sorry for that.

However, I'd like now to offer a less panicked reply. You are certainly correct that I can do what I want with a loop, but we know that recursion can do whatever iteration can; and, in a sense, I'm trying to make that abstract understanding concrete in this particular sense. Sure, I could just say 

sub f;
sub f {
    $_[0] =~ s/^(a{1,3})(?=b)/$1a/ ?
        goto &f
    :
        return $_[0];
}

[download]
to get something that only a functional programmer could love; but I'm wondering if I can make the regex perform (or ‘simulate’, of whatever) the recursion for me, without explicit function calls.

‘Regular’ regexes don't have this power, but Perl regexes are, of course, not regular; and so I could have phrased my question vaguely as: is there any way for back-references and other assorted Perl tricks to let us get around this limitations of ‘regular’ regexes?

In order to avoid under-specifying again, let me give the real question that I am trying to answer, because of moritz's post: Are Perl regexes Turing complete without (?{}) and (??{})? If not, can I get by with some minimal amount of embedded code (like (?{pos = 0}), as you suggested)?

This started off as a reply to the parent, but, while I was (slowly) composing it, you posted another node. This is my response to that node, too. :-)

In reply to Re^2: Recursive substitution by JadeNB
in thread Recursive substitution by JadeNB

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.