Using lexical filehandles seems to work for me

Yes, for relatively "flat" directory structures. There is a limit for the number of open file/directory handles (OS specific), and if the directory structure is deep enough, you will run out of file handles. That will happen even earlier if you have a lot of open files.

There is no need to keep the file/directory handle open while recursing directory structures, all you need is a single handle for arbitary nested directories:

#!/usr/bin/perl

use strict;
use warnings;

sub scan
{
        my $dirname=shift;
        opendir my $d,$dirname or die "Can't open $dirname: $!";
        my @files=readdir $d;
        closedir $d;
        for my $n (@files) {
                next if $n=~/^\.{1,2}$/;
                if (-d "$dirname/$n") {
                        print "DIR: $dirname/$n\n";
                        scan("$dirname/$n");
                } else {
                        print "NOTDIR: $dirname/$n\n";
                }
        }
}

scan(".");
[download]

There even is no need to use recursion at all:

#!/usr/bin/perl

use strict;
use warnings;

sub scan
{
        my $topdir=shift;

        my @todo=($topdir);
        while (@todo) {
                my $dirname=shift @todo;
                opendir my $d,$dirname or die "Can't open $dirname: $!
+";
                while (my $n=readdir $d) {
                        next if $n=~/^\.{1,2}$/;
                        if (-d "$dirname/$n") {
                                print "DIR: $dirname/$n\n";
                                push @todo,"$dirname/$n";
                        } else {
                                print "NOTDIR: $dirname/$n\n";
                        }
                }
                closedir $d;
        }
}

scan(".");
[download]

This way, you don't need a (possibly big) array of directory entry names for each recursion level, but only a list of directory names not yet scanned. And because this is not recursive, you won't get the "Deep recursion on subroutine" warning with deeply nested directories (see perldiag).

Try changing shift @todo to pop @todo for a different scan order.

Alexander