def replace_dict_keys(tgt_dict, map_dict):
    """
    Recursively iterates over a target dictionary and replaces existing keys
    based on map dictionary with existing keys in the target mapped to new
    values and returns a new dictionary with the keys replaced
    """
    new_dict = {}
    for key in tgt_dict.keys():
        new_key = map_dict.get(key, key)
        if isinstance(tgt_dict[key], dict):
            new_dict[new_key] = replace_dict_keys(tgt_dict[key], map_dict)
        else:
            new_dict[new_key] = tgt_dict[key]
    return new_dict