Unfortunately -f and -d won't work on an FTP server, so Net::FTP isn't going to help.
It should be possible, but you'll need to send the remote server 'pwd' and 'list' requests in order to figure out the directory structure yourself (which you should be able to do by just looking at the file permissions, and seeing it it's prefixed by a '^d' or not).
And whilst I know it's not perlish, I suggest taking a look at wget if you are trying to recurse through an ftp site.
HTH
--
It's not pessimism if there is a worse option, it's not paranoia when they are and it's not cynicism when you're right.