python递归迭代超过树实现的限制-Java 学习之路

我正在python中动态实现一棵树 . 我已经定义了一个类如下

class nodeobject():

    def __init__(self,presentnode=None,parent=None):
        self.currentNode = presentnode
        self.parentNode = parent
        self.childs = []

我有一个函数可以从池中获取每个节点的子节点

def findchildren(node, childs):` `# No need to write the whole function on how it gets childs

现在我有一个以头节点（没有父节点）开头的递归函数，并为每个节点递归地向下移动链（基本情况是没有子节点的最后一个节点）

def tree(dad,children):

    for child in children:
        childobject = nodeobject(child,dad)
        dad.childs.append(childobject)
        newchilds = findchildren(child, children)
        if len(newchilds) == 0:
            lastchild = nodeobject(newchilds,childobject)
            childobject.childs.append(lastchild)
            loopchild = copy.deepcopy(lastchild)
            while loopchild.parentNode != None:
                print "last child"
                result.append(loopchild.currentNode) # result global to store values
                loopchild = copy.deepcopy(loopchild.parentNode)
        else:
            tree(childobject,newchilds)

树形仅适用于一定数量的输入 . 一旦池变大，就会导致“最大回复深度超过”

我尝试使用set.recursionlimit（）设置递归限制，但它不起作用 . 程序崩溃了 . 我想为递归实现一个堆栈，有人可以请求帮助，即使经过很长一段时间后我也没有去过哪里？另外，除了堆栈之外还有其他方法可以解决这个问题吗？

2 回答

3
当您尝试更改递归深度时，您的程序可能会崩溃，因为您超出了系统上堆栈大小所施加的硬递归限制 . 设置sys.recursionlimit（）只会使Python对深度不那么严格，但它不会影响您的平台实际支持的内容 .

Python有一个相当天真的递归实现，这意味着它只有在你可以保证递归深度相当低时才有用 . 首先检查你的树真的足够深，可以吹掉堆栈;如果任何节点都有孩子也是他们的父母/祖先，这段代码将尝试永远运行，直到它耗尽堆栈 . 检查的一种方法是跟踪 findchildren() 返回的所有节点，并确保它们永远不会重复 .

如果您的数据正确且堆栈确实不够深，则必须将代码转换为迭代版本并手动构建自己的堆栈 . 这是你的代码有一个显式堆栈（我没有测试过，所以可能有错误，但它应该让你知道如何做到这一点）：
```
def tree(dad, children):
    stack = [(dad, children)]
    while stack:
        dad, children = stack.pop()
        for index, child in enumerate(children):
            childobject = nodeobject(child,dad)
            dad.childs.append(childobject)
            newchilds = findchildren(child, children)
            if len(newchilds) == 0:
                lastchild = nodeobject(newchilds,childobject)
                childobject.childs.append(lastchild)
                loopchild = copy.deepcopy(lastchild)
                while loopchild.parentNode != None:
                    print "last child"
                    result.append(loopchild.currentNode) # result global to store values
                    loopchild = copy.deepcopy(loopchild.parentNode)
            else:
                stack.append((dad, children[index:]))
                stack.append((childobject,newchilds))
                break
```
需要注意的一个重要特性是，在推送新的子节点之前，我们必须将尚未在for循环中处理的子节点推回堆栈 .

@Peter Gibson提出了一个很好的观点，你可能不想对你的节点进行深度复制，但是这不应该导致你的堆栈爆炸（只是耗尽大量的内存而没有我能看到的任何好处） .
回复于 2024-05-02T15:30:07+08:00
0
我会说这段代码是问题所在：
```
loopchild = copy.deepcopy(lastchild)
        while loopchild.parentNode != None:
            print "last child"
            result.append(loopchild.currentNode) # result global to store values
            loopchild = copy.deepcopy(loopchild.parentNode)
```
你遍历树直到你到达一片叶子（没有孩子的孩子），然后你把每个节点的 deepcopy 带回到开始 .

deepcopy 制作 nodeobject 的副本，以及 parentNode 的副本和 childs 中的每个子项 . 这意味着 nodeobject 的每个 deepcopy 都是 whole tree along with all of your data 的副本！

考虑一个4级深度的简单树，例如
```
A
    B           C
 D     E     F     G
H I   J K   L M   N O
```
当它到达第一片叶子 H 时，它会生成 deepcopy 个节点 H ，_ D ， B 和 A - 每个节点都是整个树和所有数据的副本 . 因此，对于这个相当简单的结构，您最终会获得32份副本！我可以看到这很快就会失去控制 .

您是否有理由制作每个节点的副本？尝试用 . 替换该代码
```
loopchild = lastchild
        while loopchild.parentNode != None:
            print "last child"
            result.append(loopchild.currentNode) # result global to store values
            loopchild = loopchild.parentNode
```
回复于 2024-05-02T15:30:07+08:00

python递归迭代超过树实现的限制

2 回答

相关问题