It's because the each is global in scope, or at least equivalent in scope to your hash. each creates an iterator that returns the next set of values on subsequent calls. You are calling each on the same hash (I'm assuming you are using a closure here), so naturally the iterator is just continuing on its merry way. I think it would make more sense here to use keys and Foreach Loops to iterate over the hash:

#!/usr/bin/perl
use strict;
use warnings;

my %hash = ( 'one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, 'five'
+ => 5);
my %dependencies =( 'one' => [], 'two' => [], 'three' => ['four'], 'fo
+ur' => ['one','two'], 'five' => ['three']);

#sub my_del($){
sub my_del{
    #while (my $key = each (%hash)){
    foreach my $key (keys %hash){
        print "KEY = $key\n";
        
        foreach (@{ $dependencies{$key} }){
            if( $_ eq $_[0]){
                print"Going to call sub for $key\n";
                my_del($key);
            }
        }
        print"\n";
    }
    delete $hash{$_[0]};
    print "Deleting $_[0]\n";
}


my_del('one');
[download]

Note that I also removed the prototyping from your function declaration as well. It's unnecessary in Perl unless you are doing particular tricks and probably doesn't mean what you think it means. Note that it can't check the prototype until the function is defined, and hence you need cleverness to protoype a function you are calling recursively.