Well a random tip then. Perl does particularly poorly when faced with deep recursion. However it certainly supports functional techniques, and I refer to several examples on my home node.

BTW I already gave a solution to a generalization of the original problem which is O(n) and has no side-effects at Re (tilly) 1: interleaving lists.