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)