递归释放循环单链表？

Question

我很好奇什么基本情况可用于递归释放循环链表，将链表的头部作为唯一参数传递。我最初认为基本情况可能 if (head->next == head) { return NULL; } 足以防止 head->next 指向自身，但事实并非如此（字面和比喻）。在此处进行递归调用后，最后一个节点 free(Head) 未被释放。

typedef struct node
{
    int data;
    struct node *next;
} node;

    // temp stores the original head of the list
    node *recursive_destroyer(node *head, node *temp)
    {
        if (head->next == temp) 
            return NULL;
    
        recursive_destroyer(head->next, temp);
    
        free(head);
        head = NULL;
    
        return NULL;
    }

Answer 1

我没有将 head 设置为等于释放整个列表的另一个函数内的 recursive_destroyer 函数。这是该函数：

LinkedList *destroy_list(LinkedList *list)
{
    node *temp;

    if (list == NULL)
        return NULL;

    if (list->head == NULL)
        return NULL;

    temp = list->head;
    
    // was not setting list->head equal to this function.
    // causing the original head to never become NULL
    list->head = recursive_destroyer(list->head, temp);

    if (list->head != NULL)
        printf("Error, head not freed.. \n");

    free(list);

    return NULL;
}

也可以将指针传递给 list->head 以避免将 list->head 设置为等于函数。

Answer 2

您的代码无效。它将使单个分配保持不变。

考虑循环链表[1]。如果你调用 recursive_destroyer(head, head)，它不会释放任何东西。正确的递归代码是

void destroy_helper(node* const current, node* const original) {
    if (current->next != original) destroy_helper(current->next, original);
    free(current);
}

void destroy(node* const list) {
    // null-check necessary since otherwise current->next is UB in destroy_helper
    if (list) destroy_helper(list, list);
}

如果我们想把它变成迭代代码，我们必须首先将destroy_helper函数修改为尾递归：

void destroy_helper(node* const current, node* const original) {
    node* const next = current->next;
    free(current);
    if (next != original) destroy_helper(next, original);
}

然后我们可以将其重写为一个循环：

void destroy(node* const list) {
    if (list) {
        node* current = list;
        do {
            node* next = current->next;
            free(current);
            current = next;
        } while (current != list);
    }
}

编辑：

为了证明我的代码实际上释放了所有东西，我们可以用下面的函数替换free：

void free_with_print(node* ptr) {
    printf("Freeing node with value %d\n", ptr->data);
    free(ptr);
}

一个简单的例子：

int main() {
    node* node1 = malloc(sizeof *node1);
    node1->data = 1;
    node1->next = node1;
    
    node* node2 = malloc(sizeof *node2);
    node2->data = 2;
    node2->next = node1;
    node1->next = node2;
    destroy(node1);
}

使用迭代版本打印

Freeing node with value 1
Freeing node with value 2

符合预期。用你的原始代码尝试同样的事情打印

Freeing node with value 1

正如预期的那样，您的代码没有释放两个节点之一，而我的代码释放了两个节点。

Answer 3

对于这样的代码，您可以（并且应该）在脑海中进行“单步调试”以说服自己它应该按预期工作。这是一项非常重要的技能。

让我们尝试3种情况：

a) 假设列表为空（head 和 temp 为 NULL）。在这种情况下，由于试图在 head->next.

中使用 NULL 指针，它会在 if (head->next == temp) 处崩溃

b) 假设列表中有一项。在这种情况下 if (head->next == temp) 是真的，因为它是一个循环链表，所以它 returns 从第一次调用开始就没有释放任何东西。

c) 假设该列表有 2 个项目。在这种情况下，if (head->next == temp) 第一次调用为 false，第二次调用为 true；所以第二次调用不会释放任何东西，第一次调用会释放列表的原始头部。

我们可以由此推断，列表中的最后一项永远不会被释放（但如果列表的原始头部的第一项不是最后一项，它将被释放）。

要解决这个问题，您可以随时释放该项目，例如：

    if (head->next == temp) {
        free(head);
        return NULL;
    }

这很麻烦，因为您在复制代码（并且可以反转条件以避免这种情况）。如果 head 始终指向原始头部并且 temp 是临时的，那么它也会更容易阅读。此外（如评论中所述）完成后返回 NULL 毫无意义。重构代码会给你这样的东西：

void recursive_destroyer(node *head, node *temp)
{
    if (head->next != temp) {
        recursive_destroyer(head, temp->next);
    }
    free(temp);
}

但是；如果列表最初是空的，这仍然会崩溃。为了解决这个问题，我会做一个包装函数，比如：

void recursive_destroyer(node *head) {
    if(head != NULL) {
        recursive_destroyer_internal(head, head);
    }
}

static void recursive_destroyer_internal(node *head, node *temp)
{

最后一个问题是递归很糟糕（由于所有额外的函数调用往往会变慢，并且当你运行出栈 space 时有崩溃的风险，并且经常最终让人们更难阅读）；特别是 if/when 编译器本身不能进行“尾调用优化”以将其转换为非递归循环。要解决这个问题，您不应该使用递归。例如：

void destroy(node *head) {
    node *original_head = head;
    node *temp;

    if(head != NULL) {
        do {
            temp = head;
            head = head->next;
            free(temp);
        } while(head != original_head);
    }
}

Answer 4

你问的是传入一个参数

我想大多数人都跳过了你的第一句话，直接跳到了你的代码。您在 post:

中询问

I'm curious what base case can be used to recursively free a circular linked list, passing the head of the linked list as the only parameter. ...

您继续解释您尝试的方法：

I originally thought a base case could be if (head->next == head) { return NULL; } could be sufficient to prevent head->next from pointing to itself, but this doesn't seem to be the case ...

你提供了一个代码示例，但是它传入了两个参数。

删除 `head->next`，而不是 `head`

这个答案是针对你第一句话中的问题。随后将与您的方法进行简短比较。

检查 head->next 是否指向 head 是一个很好的停止情况，但这意味着您的递归函数需要在每次迭代时删除和销毁 head->next，然后递归处理相同的列表。

如果head->next和head相同，那么销毁head，就完成了

我看不出从这个函数返回值有任何意义，所以我删除了它。

void recursive_destroyer(node *head) {

    if (head == NULL) return;

    if (head->next == head) {
        destroy(head);
        return;
    }

    node *tmp = head->next;
    head->next = head->next->next;
    destroy(tmp);

    recursive_destroyer(head);
}

注意递归函数不再需要第二个参数。

与你的方法比较

您的示例代码中存在一些导致错误行为的问题。还有其他一些答案已经在一定程度上解决了这些问题。但是，我确实想指出，您应该尽可能使用 尾递归。

尾递归是兄弟调用的特例。兄弟调用是指一个函数调用另一个函数，然后立即 returns。在下面的示例中，function_A() 正在对 function_B()

进行同级调用

void function_B () { puts(__func__); }

void function_A (bool flag) {
    if (flag) {
        function_B();
        return;
    }
    puts(__func__);
}

编译器可以优化同级调用，以重用当前函数的堆栈帧来进行同级调用。这是因为在兄弟 returns.

之后需要调用者当前函数状态的 none

可以用同样的方式优化尾递归调用。因此，优化后的尾递归调用与普通循环具有相同的内存占用。事实上，如果优化器检测到同级调用是递归调用，则不会对自身执行函数调用，而是将尾递归转换为跳转到函数的开头。大多数 C 编译器都可以执行此优化。您可以自己手动执行此优化，并轻松将尾递归函数转换为循环。

如果您正在使用 C 编译器的优化功能，并且它支持尾递归优化，那么在技术上没有理由更喜欢循环而不是尾递归。如果您的软件团队发现阅读递归代码令人困惑，那么首选循环只是为了让代码更容易理解。

递归释放循环单链表？

Recursively free a circular singly linked list?

c

free

recursion

circular-list

你问的是传入一个参数

删除 `head->next`，而不是 `head`

与你的方法比较

递归释放循环单链表？

Recursively free a circular singly linked list?

c

free

recursion

circular-list

你问的是传入一个参数

删除 head->next，而不是 head

与你的方法比较

删除 `head->next`，而不是 `head`