To walk a directory tree, use File::Find;.

I don't think you really want recursive functions for your problem, but there is a general page of definitions here. Recursive subs are interesting, but tend to be inefficient in perl. The canonical example is the factorial function in terms of itself:

sub factorial {
    use integer;
    die "Math error: $!" if $_[0] < 0;
    $_[0] ? $_[0] * factorial( $_[0] - 1 ) : 1 ;
}
[download]

It piles up intermediate results on the stack.

Update: Fixed silly error in the factorial function, thanks to blakem for the spot. Also made it more robust to bad input.

After Compline,
Zaxo