# Deep Merges two hashes and returns the resulting hash
# The hashes must have a similar structure - the following is an error
+:
# hash1: {a => {b => 2}}
# hash2: {a => 1}
#
sub hash_merge {
    my ($hash1,$hash2,$visited) = @_;
    # Protect against infinite recursion
    if ($visited->{$hash1} || $visited->{$hash2}) {
        return;
    }
    $visited->{$hash1} = 1;
    $visited->{$hash2} = 1;

    my %rhash = ();
    my %unique_keys = map {$_ => 0} (keys %$hash1, keys %$hash2);
    for my $key (keys %unique_keys) {
        # Store whether the key exists in each hash,
        # this makes the logic below a little more readable.
        # Note that 'exists' is checked - this is to allow
        # overrides with '0', undef, etc.
        my $e1 = exists $hash1->{$key};
        my $e2 = exists $hash2->{$key};
        if (!$e1 && $e2) {
            $rhash{$key} = $hash2->{$key};
        } elsif ($e1 && !$e2) {
            $rhash{$key} = $hash1->{$key};
        } else {
            if (ref($hash1->{$key}) eq 'HASH') {
                $rhash{$key} = hash_merge($hash1->{$key},$hash2->{$key
+},$visited);
            } else {
                $rhash{$key} = $hash2->{$key};
            }
        }
    }
    return \%rhash;
}

my %a = (
  k1 => 1,
  k2 => {
    kk3 => 3
  },
);

my %b = (
  k1 => 5,
  k2 => {
    kk4 => 4
  },
);
my $c = hash_merge(\%a,\%b);
use Data::Dumper;
$Data::Dumper::Sortkeys = 1;
print Dumper($c);
[download]

The output should be:

$VAR1 = {
          'k1' => 5,
          'k2' => {
                    'kk3' => 3,
                    'kk4' => 4
                  }
        };
[download]

This implementation is a little simplistic, but it gets the job done.