Я пытался реализовать наивные пространства имен и понял, что не понимаю, как работает рекурсия

Question

Я хотел реализовать наивные пространства имен, чтобы я мог выполнять такие запросы:

• create_namespace(namespace, parent) - добавить новое пространство имен в родительское пространство имен
• add_var(namespace, var) - добавить новую переменную в namespace
• get_var(namespace, var) - вернуть ближайшее пространство имен, в котором содержится переменная

В конце концов мне удалось реализовать первые два из них, и теперь я могу создать древовидную структуру, например:

d = {'global':{'vars': {'a'},'local':{'foo': {'vars': set(), 'local': {'foo1': {'vars': {'a'}, 'local': {}}}}, 'bar': {'vars': set(), 'local': {'foo2': {'vars': set(), 'local': {}}}}, 'baz': {'vars': set(), 'local': {'foo3': {'vars': {'a'}, 'local': {'foobar': {'vars': set(), 'local': {}}}}}}}}}

Чтобы уточнить:

get_var("foobar", "a") должен вернуться "foo3"

get_var("foo2", "a") должен вернуться "global"

Но я застрял полностью пытаясь понять, как работает рекурсия и почему иногда мы возвращаем рекурсивный вызов , а иногда просто вызываем функцию внутри себя (inte rnet не помогает, потому что я уже сыт по горло fibonacci и factorial ).

Эта реализация не работает, потому что, как я сказал, я просто не могу понять, почему мои возвращаемые значения теряются, когда callstack не набран:

def get_var(namespace, var):
    def go_deeper(dic, location=None):
        if dic == {} or location == namespace:
            return location
        for (name, ns) in dic.items(): #iterate over namespaces within parent namespace
            if var in ns["vars"]:      
                go_deeper(ns["local"], name) #if we found variable *var* we remember its location by passing it as an argument 
            else:
                go_deeper(ns["local"], location) #otherwise we keep using previous found *location*
    return go_deeper(d)

Answer 1

Я предлагаю другое решение с двумя различными рекурсивными функциями.

def get_var(search_namespace, var, dict):
    for dict_namespace, sub_dict in dict.items():
        vars = sub_dict['vars']
        locals = sub_dict['local']

        # recursively search search_namespace in locals
        found_namespace = get_var(search_namespace, var, locals)
        if found_namespace is not None:
            return found_namespace
        # search if current namespace is a solution
        if var in vars and dict_contains(search_namespace, locals):
            return dict_namespace

    return None

def dict_contains(searched_key, dictionary):
    if not isinstance(dictionary, dict):
        return False
    return any(key==searched_key or dict_contains(searched_key, value)
                for key, value in dictionary.items())

Answer 2

Проблема с вашей функцией, как вы сказали, заключается в том, что «я просто не могу понять, почему мои возвращаемые значения теряются, когда вызов стека отменяется». Одним из важных моментов, связанных с рекурсивной функцией, является возможность получения результата, найденного глубоко в вызовах, который «передается» обратно к исходному вызову функции. Этот случай не был тривиальным, в отличие от факториалов или фибоначчи.
На самом деле вы были довольно близки: -)
Решение состоит в том, чтобы при углублении в «дерево» проверить, находится ли искомое пространство имен действительно присутствует, при этом отслеживая ближайшего родителя, который содержал переменную. Затем можно «передать» имя этого ближайшего родителя вверх по стеку.
Вы можете сделать это следующим образом:

def get_var(namespace, var):
    def go_deeper(dic, location=None):
        if namespace in dic:  # the namespace has been found, return the 'location'
            if var in dic[namespace]['locals']:  # check that the namespace itself does not contain the car, who knows
                return namespace
            else:
                return location
        for (name, ns) in dic.items():
            if var in ns["vars"]:
                result = go_deeper(ns["local"], name)
                if result is not None:
                    return result  #  if the namespace was found deeper, return/transmit the result('location') along the call stack
            else:
                res = go_deeper(ns["local"], location)
                if result is not None:
                    return result  # idem
        # return None  (the default behavior of a python function)
    return go_deeper(d)

Небольшой совет: на самом деле dict очень трудно читать для человека. В стандартной python lib есть небольшая утилита, называемая pprint , которая позволяет красиво печатать вложенные структуры данных с отступами. Я мог понять основную структуру d только когда увидел это так:

pprint.pprint(d)
{'global': {'local': {'bar': {'local': {'foo2': {'local': {}, 'vars': set()}},
                              'vars': set()},
                      'baz': {'local': {'foo3': {'local': {'foobar': {'local': {},
                                                                      'vars': set()}},
                                                 'vars': {'a'}}},
                              'vars': set()},
                      'foo': {'local': {'foo1': {'local': {}, 'vars': {'a'}}},
                              'vars': set()}},
            'vars': {'a'}}}