时间戳

首页 > 解决方案 > 我试图实现幼稚的命名空间并意识到我不明白递归是如何工作的

python-3.x - 我试图实现幼稚的命名空间并意识到我不明白递归是如何工作的

问题描述

我想实现简单的命名空间，以便可以进行这样的查询：

最终我设法实现了前两个，所以我现在可以创建一个像这样的树结构：

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"

但是当我试图理解递归是如何工作的以及为什么有时我们返回递归调用而有时只是调用自身内部的函数时，我完全陷入了困境（互联网没有帮助，因为我已经厌倦了fibonacci和factorial）。

这个实现不起作用，因为正如我所说，我无法理解为什么我的返回值在调用堆栈展开时会丢失：

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)

标签： python-3.xrecursiontree

解决方案

正如您所说，您的函数的问题是“我不明白为什么我的返回值在调用堆栈展开时会丢失”。递归函数的关键点之一是能够将在调用深处发现的结果“传输”回原始函数调用。与阶乘或斐波那契不同，这种情况并非微不足道。
实际上，您非常接近:-)
解决方案是在“树”中深入时检查您正在寻找的命名空间是否确实存在，同时跟踪包含变量的最近父级。然后设法将这个最接近的父母的名字“传输”到堆栈中。
你可以这样做：

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 库中有一个名为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'}}}

推荐阅读