Move the statement handlers outside the recursive function. Then, instead of passing a dbh, you pass the properly initialized statement handlers;

In addition, you should change the fetch method, so you are sure that the recursed sth is not executing a nested operation while still handling the outer one.

This is untested but it should get you on track.

sub rebuild_tree
{
    my $sth1 = shift;
    my $sth2 = shift;
    my $dir_ID = shift;
    my $left = shift;

    my $right = $left + 1;

    $sth1->execute($dir_ID) || return $right + 1;
    my $recs = $sth1->fetchall_arrayref();

    for my $row (@$recs)
    {
        $right = rebuild_tree($sth1,$sth2, $row->[0], $right);
    }

    $sth2->execute($left, $right, $dir_ID);
    return $right + 1;
}

my $sql1 = "select ID, name from DIRECTORIES where parent_ID = ?";
my $sth1 = $dbh->prepare($sql1);

my $sql2 = "update DIRECTORIES set lft = ?, rght = ? where ID = ?";
my $sth2 = $dbh->prepare($sql2);

my ($dir_ID, $left) = (); # whatever you need
my $right = rebuild_tree($sth1, $sth2, $dir_ID, $left );
[download]

Update
I remember now that have seen this approach before in one of Joe Celko's tricks in this article, which uses stored procedures to update the tree.

 _  _ _  _  
(_|| | |(_|><
 _|