我的 C 递归函数是如何工作的？

Question

我用 C 语言编写了一个递归函数，以释放生成节点树的程序所分配的内存。然而，我无法弄清楚它是如何工作的 - 但它确实通过了 check50。也许我写得不够好，我无法理解。

我尝试过跟踪调试器，但我就是无法理解它如何成功地遍历 3 代父母。

我想我的主要问题是：

1. 这个函数如何从祖先树的底部到顶部释放出来？例如。

   free(p)

   如何以及何时被调用？是在调用 return 的时候吗？我知道不要孤立任何节点很重要，但我不知道这里如何避免这种情况。

2. 跟随调试器并逐步执行代码，

   free(p)

   显然不会被调用，直到看起来到达祖父母节点 - 例如

   free_family(p->parents[0])

   已被调用两次，然后在

   p->parents[0]

   从调用中释放该堆栈之前，对

   free(p)

   的后续调用为 NULL。我根本不明白这是如何工作的。

对菜鸟问题表示歉意 - 我目前是编码新手并关注 CS50x。

除非需要，我不会发布整个代码，但每个节点都是由以下代码定义的。这些节点共有 3 代。最后一代父母收到 NULL 父母指针。

typedef struct person
{
    struct person *parents[2];
    char alleles[2];
} person;

我的递归自由函数是：

// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
    // TODO: Handle base case

    if (p == NULL)
    {
        return;
    }

    // TODO: Free parents recursively

    free_family(p->parents[0]);
    free_family(p->parents[1]);

    // TODO: Free child

    free(p);
}

Answer 1

person1
  |- person2
  |    |- person4
  |    |- person5
  |- person3
  |    |- person6
  |    |- person7

假设这是您的树。它是倒置的 - person1 是最小的，其父母为 person2 和 person3。

当您转到 free person1 时，您的代码将执行以下操作：

 - Want to free person1, but the parents are to be freed first
 - Try to free person2
    - Try to free person4
        - person4 has no first parent, so no more recursion. Free person4
    - Try to free person5
        - person5 has no second parent, so no more recursion. Free person5
 - Now that yo're done freeing the parents of person2, you actually free person2
 - Repeat above for person3
 - Now that you are done freeing the parents for person1, actually free person1

这实际上相当简单。要理解它，您需要做的是遵循控制流程。花一些时间研究代码本身，并尝试逐行遵循控制流程。这不是异步或线程代码，并且具有非常线性的执行序列。尽量不要迷失在调试器中。只有在很好地掌握了控制流的正常工作原理之后，您才能有效地使用调试器。