import copy


def merge_facts(orig, new):
    """ Recursively merge facts dicts

        Args:
            orig (dict): existing facts
            new (dict): facts to update
        Returns:
            dict: the merged facts
    """
    facts = dict()
    for key, value in orig.iteritems():
        if key in new:
            if isinstance(value, dict):
                facts[key] = merge_facts(value, new[key])
            else:
                facts[key] = copy.copy(new[key])
        else:
            facts[key] = copy.deepcopy(value)
    new_keys = set(new.keys()) - set(orig.keys())
    for key in new_keys:
        facts[key] = copy.deepcopy(new[key])
    return facts