Why be functional when you can be efficient? Recursion might be elegant, but computers don't really understand elegance. :) Functional programming has a lot of great and useful concepts in it, and luckily we use a language that doesn't *force* us to be purists about it.
P.S.: The variable assignment is very necessary in my second example, because otherwise you're going to get a circularly referenced subroutine, which will make perl hit a infinite recursion warning pretty damned quick.
P.P.S: And, you're right, your last version is even better!