了解在重复函数中内置到变量赋值中的多个递归调用

Question

我有一个二进制树的对象,由递归函数构建.我试图理解这里的递归调用:

def buildDTree(sofar, todo):
    if len(todo) == 0:
        return binaryTree(sofar)
    else:
        withelt = buildDTree(sofar + [todo[0]], todo[1:])
        withoutelt = buildDTree(sofar, todo[1:])
        here = binaryTree(sofar)
        here.setLeftBranch(withelt)
        here.setRightBranch(withoutelt)
        return here

现在,我不明白的是函数内部语句的执行顺序.具体来说,我不理解变量赋值语句及它们的分配顺序以及它们的分配顺序.

现在,我确实理解了树结构,如何创建类,以及使用return语句启动递归,python中的递归函数有多简单.

如果您感兴趣,树对象是:

class binaryTree(object):
    def __init__(self, value):
        self.value = value
        self.leftBranch = None
        self.rightBranch = None
        self.parent = None 
    def setLeftBranch(self, node):
        self.leftBranch = node
    def setRightBranch(self, node):
        self.rightBranch = node
    def setParent(self, parent):
        self.parent = parent
    def getValue(self):
        return self.value
    def getLeftBranch(self):
        return self.leftBranch
    def getRightBranch(self):
        return self.rightBranch
    def getParent(self):
        return self.parent
    def __str__(self):
        return self.value

使用以下变量和赋值语句调用buildDTree函数:

a = [6,3]
b = [7,2]
c = [8,4]
d = [9,5]

treeTest = buildDTree([], [a,b,c,d])

Answer 1

好吧,当你不理解代码时,方法总是一样的:运行代码就像你是计算机一样.即创建一个包含所有变量的表并执行每行代码并将每个变量修改下来.

buildDTree(sofar=[], todo=[[6,3],[7,2],[8,4],[9,5]]):

| sofar | todo                        |
| ----- | --------------------------- |
| `[]`  | `[[6,3],[7,2],[8,4],[9,5]]` |

len(todo) == 0 ? false
withelt = buildDTree(sofar + [todo[0]], todo[1:])

    | sofar      | todo                  |
    | ---------- | --------------------- |
    | `[[6,3]]`  | `[[7,2],[8,4],[9,5]]` |

    len(todo) == 0 ? false
    withelt = buildDTree(sofar + [todo[0]], todo[1:])

        | sofar            | todo            |
        | ---------------- | --------------- |
        | `[[6,3],[7,2]]`  | `[[8,4],[9,5]]` |

        len(todo) == 0 ? false
        withelt = buildDTree(sofar + [todo[0]], todo[1:])

            | sofar                   | todo      |
            | ----------------------- | --------- |
            | `[[6,3],[7,2],[8,4]]]`  | `[[9,5]]` |

            len(todo) == 0 ? false
            withelt = buildDTree(sofar + [todo[0]], todo[1:])

                | sofar                        | todo |
                | ---------------------------- | ---- |
                | `[[6,3],[7,2],[8,4],[9,5]]`  | `[]` |

                len(todo) == 0 ? true
                return binaryTree(sofar)

            | sofar                   | todo      | withelt                                       |
            | ----------------------- | --------- | --------------------------------------------- |
            | `[[6,3],[7,2],[8,4]]]`  | `[[9,5]]` | `binaryTree(value=[[6,3],[7,2],[8,4],[9,5]])` |

            withoutelt = buildDTree(sofar, todo[1:])

                | sofar                  | todo |
                | ---------------------- | ---- |
                | `[[6,3],[7,2],[8,4]]`  | `[]` |

                len(todo) == 0 ? true
                return binaryTree(sofar)

            | sofar                   | todo      | withelt                                       | withoutelt                              |
            | ----------------------- | --------- | --------------------------------------------- | --------------------------------------- |
            | `[[6,3],[7,2],[8,4]]]`  | `[[9,5]]` | `binaryTree(value=[[6,3],[7,2],[8,4],[9,5]])` | `binaryTree(value=[[6,3],[7,2],[8,4]])` |

            here = binaryTree(sofar)

            | sofar                   | todo      | withelt                                       | withoutelt                              | here                                    |
            | ----------------------- | --------- | --------------------------------------------- | --------------------------------------- | --------------------------------------- |
            | `[[6,3],[7,2],[8,4]]]`  | `[[9,5]]` | `binaryTree(value=[[6,3],[7,2],[8,4],[9,5]])` | `binaryTree(value=[[6,3],[7,2],[8,4]])` | `binaryTree(value=[[6,3],[7,2],[8,4]])` |

            here.setLeftBranch(withelt)
            here.setRightBranch(withoutelt)

            | sofar                   | todo      | withelt                                       | withoutelt                              | here                                                          |
            | ----------------------- | --------- | --------------------------------------------- | --------------------------------------- | ------------------------------------------------------------- | 
            | `[[6,3],[7,2],[8,4]]]`  | `[[9,5]]` | `binaryTree(value=[[6,3],[7,2],[8,4],[9,5]])` | `binaryTree(value=[[6,3],[7,2],[8,4]])` | `binaryTree(value=[[6,3],[7,2],[8,4]]`                        |
            |                         |           |                                               |                                         |              left=binaryTree(value=[[6,3],[7,2],[8,4],[9,5]]) |
            |                         |           |                                               |                                         |             right=binaryTree(value=[[6,3],[7,2],[8,4]]))      |

            return here

        | sofar            | todo            | withelt                                                       |
        | ---------------- | --------------- | --------------------------------------------------------------|
        | `[[6,3],[7,2]]`  | `[[8,4],[9,5]]` | `binaryTree(value=[[6,3],[7,2],[8,4]]`                        |
        |                  |                 |              left=binaryTree(value=[[6,3],[7,2],[8,4],[9,5]]) |
        |                  |                 |             right=binaryTree(value=[[6,3],[7,2],[8,4]]))      |

        withoutelt = buildDTree(sofar, todo[1:])

        ...
    ...
...

我没有完成,因为我确实有自己的工作,因为无论如何,你最好完成这项工作.我希望你有这背后的想法.我知道递归时的递归感觉有多么棘手,但最后,这只是方法论的问题.

HTH