import copy


def deep_merge_dict(base, priority):
    """Recursively merges the two given dicts into a single dict.

    Treating base as the the initial point of the resulting merged dict,
    and considering the nested dictionaries as trees, they are merged os:
    1. Every path to every leaf in priority would be represented in the result.
    2. Subtrees of base are overwritten if a leaf is found in the
    corresponding path in priority.
    3. The invariant that all priority leaf nodes remain leafs is maintained.


    Parameters
    ----------
    base : dict
        The first, lower-priority, dict to merge.
    priority : dict
        The second, higher-priority, dict to merge.

    Returns
    -------
    dict
        A recursive merge of the two given dicts.

    Example:
    --------
    >>> base = {'a': 1, 'b': 2, 'c': {'d': 4}, 'e': 5}
    >>> priority = {'a': {'g': 7}, 'c': 3, 'e': 5, 'f': 6}
    >>> result = deep_merge_dict(base, priority)
    >>> print(sorted(result.items()))
    [('a', {'g': 7}), ('b', 2), ('c', 3), ('e', 5), ('f', 6)]
    """
    if not isinstance(base, dict) or not isinstance(priority, dict):
        return priority
    result = copy.deepcopy(base)
    for key in priority.keys():
        if key in base:
            result[key] = deep_merge_dict(base[key], priority[key])
        else:
            result[key] = priority[key]
    return result