Recursively free a circular singly linked list?

Question

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 (literally and figuratively). The last node free(Head) is not being freed after the recursive calls here.

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

You asked about passing in one parameter

I think most people skipped your first sentence, and jumped to your code. You ask in your 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. ...

You go on to explain the approach you tried:

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 ...

You provide a code example, but it passes in two parameters.

Remove head->next, not head

This answer is addressing the question in your first sentence. A short comparison with your approach will follow.

Checking to see if head->next points to head is a fine stopping case, but it means your recursive function needs to remove and destroy head->next at each iteration, and then recursively process the same list.

If head->next and head are the same, then destroy head, and you are done.

I don't see any point of returning a value from this function, so I removed it.

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);
}

Notice there is no longer any need for a second parameter to the recursive function.

Comparison with your approach

There are some issues in your sample code that caused erroneous behavior. There are other answers that have addressed them with some depth. But, I did want to point out that you should prefer tail recursion whenever possible.

Tail recursion is a special case of a sibling call. A sibling call is when a function calls another function, and then immediately returns. In the example below, function_A() is making a sibling call to function_B()

void function_B () { puts(__func__); }

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

A sibling call can be optimized by the compiler to reuse the stack frame of the current function to make the sibling call. This is because none of the current function state of the caller is needed after the sibling returns.

A tail recursive call can be optimized in the same way. Thus, the tail recursive call when optimized has the same memory footprint as an ordinary loop. And in fact, if the optimizer detects the sibling call is a recursive call, instead of performing a function call to itself, the tail recursion is converted into a jump to the start of the function. Most C compilers can perform this optimization. You can manually perform this optimization yourself, and easily convert a tail recursive function into a loop.

If you are using the optimization features of your C compiler, and it supports tail recursion optimization, then there is no technical reason to prefer a loop over tail recursion. If your software team finds reading recursive code confusing, then loops are preferred just to make the code easier to comprehend.