为什么此递归函数会迅速增加内存使用？

Question

我在Python中编写了以下递归函数，以为list的str值建立索引（在列表中可能多次重复相同的值）。该函数接受list并返回dict，其中字典的每个条目都是项目列表（str）和相应的int索引。

def make_indices(entries):
    def _make_indices(ent, idxs, idx):
        if not ent:
            return idxs
        else:
            _make_indices(ent[1:], idxs, idx) if ent[0] in idxs \
                else _make_indices(ent[1:], dict({ent[0]: idx}, **idxs), idx+1)
    return _make_indices(entries, {}, 0)

我以为这将是一个不错的解决方案，但是它的内存使用量随着列表的长度迅速增加。有人能够解释到底是什么会导致这种过多的内存使用吗？

Answer 1

切片列表ent[1:]，将导致重新分配切片部分的浅表副本。另外，由于Python无法优化尾端递归，因此您将处于这样一个情况，即您制作的每个单个切片都将保持分配状态，直到外部调用终止为止。

尝试改用ent.pop(0)删除列表的第一个元素，然后将列表作为ent传递而不进行切片。这样，不需要新分配]