on my first script (I'm still a newbie) I had the same problem. I have solved it in this way:

use DirHandle;
use Cwd;
use File::stat;

$strarting_dir = cwd;

&creaalbero($strarting_dir);
&alkilo($dimensione);

print $dimensione;

sub creaalbero
{
    chdir $_;
    $cwd = cwd;
    $percorso = "$cwd"."\\";
    $dh = new DirHandle;
    $dh->open("$_");
    @lista = ($dh->read());
    shift @lista;
    shift @lista;
    foreach $dir (<*>)
    {
        if (-d $dir)
        {
            chdir $dir;
            &creaalbero();
            $albero{"$percorso"} = directory;
            chdir"..";
        }

        if (-f $dir)
        {
            $current = cwd;
            $albero{"$current"."\\"."$dir"} = file;
            $stat = stat ($dir);
            $dimensione += $stat->size;
        }

    }
}

sub alkilo
{
    $dimensione = $dimensione / 1024;
    @grand = qw/Tb Gb Mb Kb /;
    if ( $dimensione >= 1024 ) { pop @grand ; &alkilo($dimensione) }
    unless ( $dimensione == 0 ) { $molt = pop @grand }
    $dimensione =~ /^\d*\.\d?\d?/;
    $dimensione = "$&" . " " . "$molt";
}
[download]

This code make %albero with the paths as keys and directory or file as values(is unnecessary to recurse the directory).
It calculate the size of the sub tree and print out the value.
The magic point is:

foreach $dir(<*>)
[download]

NOTE: creaalbero means maketree and percorso means path.

seeU L*