How can this left-recurse? Can you give an example? I thought regular expressions weren't recursive at all.

The Kleene star is a fixed-point/recursion operator. Here's an example that causes an infinite loop:

    (|a)*

That's not left-recursion.

I probably shouldn't have used the 'left' adjective. But that expression results in an unproductive recursion (unproductive meaning that no characters are consumed through each cycle) analogous to what happens when you recursive-descent parse a context-free grammar containing left-recursive productions.

They're not, most 'regex' engines today aren't actually regular.