The map solution was so cool and perlish that I had to try recursion with it!

sub perlish {
    chomp;

    $_ = realpath($_); # follows links, makes full path

    ( -d )
    ? ( $processed{$_}
        ? ()
        : do {
            my $basedir = $_;
            $processed{$_} = 1; # prevent infinite recursion into link
+s

            # turn results of ls into relative paths before recursion
            # and avoids using chdir
            map &perlish, ( map {"$basedir/$_"} `ls $_` );
        }
      )
    : $_;
}

%processed = ( getcwd() => 1 );
print join "\n", (map &perlish, `ls`),"\n";
[download]

I love recursive maps now! It is MUCH prettier if you don't have to worry about symbolic links to dirs you already checked or relative paths:

sub perlish {
    chomp;
    ( -d ) ? map &perlish, `find $_/* -maxdepth 0` : $_;
}
my @files = map &perlish, `find . -maxdepth 0`;
[download]