理解递归函数中变量赋值中内置的多个递归调用

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

现在，我不明白的是函数内部语句的执行顺序。具体地说，我不理解变量赋值语句以及它们将被赋值的顺序以及它们将被赋值的内容。在

现在我了解了树结构，类是如何生成的，以及在python中如何使用return语句启动递归的更简单的递归函数。在

如果您感兴趣，树对象是：

^{pr2}$

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

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

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

Answer 1

好吧，当你不懂代码时，方法总是一样的：把代码当作计算机来运行。i、 制作一个包含所有变量的表，执行每一行代码并写下每个变量的修改。在

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:])

        ...
    ...
...

我没有完成，因为我有自己的工作，而且不管怎样，你最好完成这件事。我希望你知道这背后的想法。 我知道递归开始时会有多棘手，但最终，这只是一个方法论问题。在

高温