时间戳

首页 > 解决方案 > 如何调试递归调用的函数？

python - 如何调试递归调用的函数？

问题描述

我正在尝试编写一个函数，该函数在任意深度的嵌套中搜索一个键dict并将其值与祖先键的路径一起返回 -

# find_key.py
def find_key(key, targ, path=[]):
    """ Search an aribitarily deep nested dict `targ` for key `key`.
        Return its value(s) together with the path(s) of ancestor keys.
    """
    if key == targ:
        yield v, path
    if isinstance(targ, dict):
        for k, v in targ.items():
            if k == key:
                yield v, path
            else:
                find_key(key, v, path.append(k))
                path.pop()

# test code
targ_1 = {'a': 1, 'b': {'b': 2, 'c': 3}, 'd': {'e': {'f': 4}}}
tests = {'test_a': {'key' : 'a', 'targ': targ_1, 'expect': [(1, [])]},
         'test_b': {'key' : 'b', 'targ': targ_1, 'expect': [({'b': 2, 'c': 3}, []), (2, ['b'])]},
         'test_c': {'key' : 'c', 'targ': targ_1, 'expect': [(3, ['b'])]},
         'test_d': {'key' : 'd', 'targ': targ_1, 'expect': [({'e': {'f': 4}}, [])]},
         'test_e': {'key' : 'e', 'targ': targ_1, 'expect': [({'f': 4}, ['d'])]},
         'test_f': {'key' : 'f', 'targ': targ_1, 'expect': [(4, ['d', 'e'])]}}
for k, v in tests.items():
    if list(find_key(v['key'], v['targ'])) == v['expect']:
        print(k, 'OK')
    else:
        print(k, 'actual:', list(find_key(v['key'], v['targ'])))
        print(k, 'expected:', v['expect'])

执行代码显示很多测试用例都失败了——

(3.8) $ python find_key.py 
test_a OK
test_b actual: [({'b': 2, 'c': 3}, [])]
test_b expected: [({'b': 2, 'c': 3}, []), (2, ['b'])]
test_c actual: []
test_c expected: [(3, ['b'])]
test_d OK
test_e actual: []
test_e expected: [({'f': 4}, ['d'])]
test_f actual: []
test_f expected: [(4, ['d', 'e'])]

我怀疑问题出在递归调用上find_key，所以我在调用上方插入了一个breakpoint()并重新执行了文件-

(3.8) $ python find_key.py 
> find_key.py(15)find_key()
-> find_key(key, v, path.append(k))
(Pdb) s
--Call--
> find_key.py(1)find_key()
-> def find_key(key, targ, path=None):
(Pdb) s
GeneratorExit
> find_key.py(1)find_key()
-> def find_key(key, targ, path=None):
(Pdb) s
--Return--
> find_key.py(1)find_key()->None
-> def find_key(key, targ, path=None):
(Pdb) s
> find_key.py(16)find_key()
-> path.pop()
(Pdb)

如您所见，Pdb 并没有进入递归调用find_key，而是发出消息GeneratorExit和--Return--. 我该如何调试这个问题？

标签： pythonpython-3.xdebuggingrecursion

解决方案

人脑调试

# find_key.py
def find_key(key, targ, path=[]):
    """ Search an aribitarily deep nested dict `targ` for key `key`.
        Return its value(s) together with the path(s) of ancestor keys.
    """
    if key == targ:
        yield v, path
    if isinstance(targ, dict):
        for k, v in targ.items():
            if k == key:
                yield v, path
            else:
                find_key(key, v, path.append(k))
                path.pop()

targ_1 = {'a': 1, 'b': {'b': 2, 'c': 3}, 'd': {'e': {'f': 4}}}
list(find_key("b", targ_1))

让我们简单地使用我们的人脑评估器评估程序 -

key = "b"
targ = {'a': 1, 'b': {'b': 2, 'c': 3}, 'd': {'e': {'f': 4}}}
path = []
# if key == targ:
#    yield v, path
if isinstance(targ, dict):
    for k, v in targ.items():
        # ("a", 1)
        # ("b", {'b': 2, 'c': 3})
        # ("d", {'e': {'f': 4}})
        k = "a"
        v = 1
        # if k == key:
            # yield v, path
        else:
            find_key(key, v, path.append(k)) # path = ["a"]
            path.pop()                       # path = []

在for循环的第一次迭代中，k不等于key所以我们运行else程序的分支。find_key返回一个生成器，但我们不使用它做任何事情。即，不使用return或yield from使用。所以无论它做什么，我们都可以完全忽略它，因为它不会出现在我们函数的输出中。要理解我的意思，请考虑以下示例 -

def foo():
  1+10      # missing yield or return

foo()

None

在上面的程序中，foo将评估1+10但没有任何反应，所以它被忽略了。find_key这与在不使用返回值的情况下调用函数是一样的——python 会评估它，但结果会立即被丢弃。现在让我们进入第二次迭代 -

key = "b"
targ = {'a': 1, 'b': {'b': 2, 'c': 3}, 'd': {'e': {'f': 4}}}
path = []
# if key == targ:
#    yield v, path
if isinstance(targ, dict):
    for k, v in targ.items():
        # ("a", 1)
        # ("b", {'b': 2, 'c': 3})
        # ("d", {'e': {'f': 4}})
        k = "b"
        v = {'b': 2, 'c': 3}
        if k == key:
            yield v, path            # ({'b': 2, 'c': 3}, [])
        # else:
            # find_key(key, v, path.append(k)) # path = ["a"]
            # path.pop()                       # path = []

上面，我们看到了for循环的第二次迭代。在这里k == key，所以现在我们yield。请注意，因为您使用else关键字，所以我们不会 recur find_key。这意味着没有尝试key = "b"在v.

key = "b"
targ = {'a': 1, 'b': {'b': 2, 'c': 3}, 'd': {'e': {'f': 4}}}
path = []
# if key == targ:
#    yield v, path
if isinstance(targ, dict):
    for k, v in targ.items():
        # ("a", 1)
        # ("b", {'b': 2, 'c': 3})
        # ("d", {'e': {'f': 4}})
        k = "d"
        v = {'e': {'f': 4}}
        # if k == key:
            # yield v, path
        else:
            find_key(key, v, path.append(k)) # path = ["d"]
            path.pop()                       # path = []

在for循环的第三次迭代中，它与第一次相同。k不等于key，因此find_key被调用，结果被忽略。

输出很容易确定。第二次迭代 wherek == "b"是我们函数的唯一输出。由于您将find_key调用包装在其中，list(...)这是我们将在列表中看到的唯一结果 -

[({'b': 2, 'c': 3}, [])]

解决问题

这是我注意到的事情 -

  1. 在yield from递归调用find_key.
  2. 条件逻辑可以简化
  3. 使用else可防止对值 进行递归v，其中k == key
  4. 避免变异.append并使.pop算法的推理更容易
def find_key(key, targ, path = []):
  """ Search an aribitarily deep nested dict `targ` for key `key`.
      Return its value(s) together with the path(s) of ancestor keys.
  """
  if isinstance(targ, dict):
    for (k,v) in targ.items():
      if k == key:
        yield (v, path)
      yield from find_key(key, v, [*path, k])  # <- no else, yield from

test_a OK
test_b OK
test_c OK
test_d OK
test_e OK
test_f OK

路径参数

您也可以选择从签名中删除path参数-find_key

# find_key.py
def find_key(key, targ):                  # <- no path arg
  """ Search an aribitarily deep nested dict `targ` for key `key`.
      Return its value(s) together with the path(s) of ancestor keys.
  """
  if isinstance(targ, dict):
    for (k,v) in targ.items():
      if k == key:
        yield (v, [])                     # <- empty path
      for (v, path) in find_key(key, v):  # <- get path from recursive result
        yield (v, [k, *path])             # <- prepend path

直系祖先

最后，我认为直接祖先没有出现在结果中很奇怪。IE，

list(find_key("a", {"a":1}))

[(1, [])]

根据上面的结果，到的路径1是空的，[]。我希望结果是[(1, ["a"])]. 即，路径1是targ["a"]。这是一个简单的改变 -

# find_key.py
def find_key(key, targ):
  """ Search an aribitarily deep nested dict `targ` for key `key`.
      Return its value(s) together with the path(s) of ancestor keys.
  """
  if isinstance(targ, dict):
    for (k,v) in targ.items():
      if k == key:
        yield (v, [k])                    # <- base path
      for (v, path) in find_key(key, v):
        yield (v, [k, *path])

list(find_key("b", targ_1))

路径{'b': 2, 'c': 3}是targ["b"]
路径2是targ["b"]["b"]

[({'b': 2, 'c': 3}, ['b']), (2, ['b', 'b'])]

推荐阅读