I think these 2 patterns

/(.(?1)(*F))/ /(.*)(*F)/

should backtrack about the same amount.

Nope, seems like the first has quadratic and the second one linear complexity. 
use v5.12;
use warnings;


say my $az = join "","a".."z";
$az x= 100;

my $c;
my $show=0;
sub COUNT {
  $c++;
  say "Step $c matches '",$2 // "","'"
    if $show;
}
$show=0;
for my $l (1..24)

  {
  say "=== Length Str: ",$l;
  my $str = substr $az,0,$l;
  $c = 0;
  $str =~ /( (.) (?{COUNT}) (?1) (*FAIL))/x; 
  say "$l : $c = ", $l*($l+1)/2;
  $c=0;
  $str =~ /( (?: (.) (?{COUNT}) )* (*FAIL) )/x;
  say "$l : $c = ", 2 *$l-1;
}

[download]
output 
# perl /home/lanx/perl/pm/recursive_regex.pl
abcdefghijklmnopqrstuvwxyz
=== Length Str: 1
1 : 0 = 1
1 : 1 = 1
=== Length Str: 2
2 : 3 = 3
2 : 3 = 3
=== Length Str: 3
3 : 6 = 6
3 : 5 = 5
=== Length Str: 4
4 : 10 = 10
4 : 7 = 7
=== Length Str: 5
5 : 15 = 15
5 : 9 = 9
=== Length Str: 6
6 : 21 = 21
6 : 11 = 11
=== Length Str: 7
7 : 28 = 28
7 : 13 = 13
=== Length Str: 8
8 : 36 = 36
8 : 15 = 15
=== Length Str: 9
9 : 45 = 45
9 : 17 = 17
=== Length Str: 10
10 : 55 = 55
10 : 19 = 19
=== Length Str: 11
11 : 66 = 66
11 : 21 = 21
=== Length Str: 12
12 : 78 = 78
12 : 23 = 23
=== Length Str: 13
13 : 91 = 91
13 : 25 = 25
=== Length Str: 14
14 : 105 = 105
14 : 27 = 27
=== Length Str: 15
15 : 120 = 120
15 : 29 = 29
=== Length Str: 16
16 : 136 = 136
16 : 31 = 31
=== Length Str: 17
17 : 153 = 153
17 : 33 = 33
=== Length Str: 18
18 : 171 = 171
18 : 35 = 35
=== Length Str: 19
19 : 190 = 190
19 : 37 = 37
=== Length Str: 20
20 : 210 = 210
20 : 39 = 39
=== Length Str: 21
21 : 231 = 231
21 : 41 = 41
=== Length Str: 22
22 : 253 = 253
22 : 43 = 43
=== Length Str: 23
23 : 276 = 276
23 : 45 = 45
=== Length Str: 24
24 : 300 = 300
24 : 47 = 47

[download]
Reason: Perl regex are highly pre-optimized by using heuristics.

HTH

- LanX (Log In Timed out)

In reply to Re^2: Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?) by LanX
in thread Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?) by Anonymous Monk

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.