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.
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->, $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 );
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.