How does this recursive delete node function work?

Question

I'm a little confused on the order of this function. It takes in a struct node pointer and free's each node until there are no nodes left (I think). What I don't understand is if we recursively call recursive_destroyer(), I don't understand how the function will reach free(head). Same with the destroy_list() function. Doesn't calling the recursive function restart the function? Here is the code: Also, Node and LinkedList are structs that aren't included here, just for reference.

node *recursive_destroyer(node *head) // takes in node and deletes each node
{
  if (head == NULL) // if there are no nodes
    return NULL;

  recursive_destroyer(head->next); // cycle through each node
  free(head);

  return NULL;
}

LinkedList *destroy_list(LinkedList *list)
{
  if (list == NULL)
    return NULL;

  recursive_destroyer(list->head);
  free(list);

return NULL;
}

At some point, a recursive call to `recursive_destroyer` will *not* call itself & *will* immediately return, so the caller will then proceed to call `free(head)`, as will the call to *it*, etc. — Scott Hunter, Oct 23 '20 at 18:53
`recursive_destroyer(head->next);` will keep being called moving to the end of the list. Only then will it sort of run backwards, and all the calls to `free(head);` get executed. — 001, Oct 23 '20 at 18:53
Tracing how a recursive function works is a *great* use of a debugger. — Scott Hunter, Oct 23 '20 at 18:54
@JohnnyMopp Meaning if there is no head->next node, and only the head is left, then it will call free()? — idkusrname126, Oct 23 '20 at 18:57
"Doesn't calling the recursive function restart the function?" No, it doesn't. It calls a *copy* of the function. Making a recursive call is not any different from making any other function call. See this question: [Understanding how recursive functions work](https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work/25677060) — Stef, Oct 23 '20 at 19:03
@stef maybe *instance* would be a better word than *copy*? The current state of local variables doesn't get copied. — HAL9000, Oct 23 '20 at 19:05
Just a side note. Using recursion to free nodes in a linked list is a very good way to learn about recursion. But in the real world it is a dangerous and ineffective way to free the nodes. — HAL9000, Oct 23 '20 at 19:10

001 · Answer 1 · 2020-10-23T19:14:53.763

Let's say there are 3 nodes: node_1 -> node_2 -> node_3 The sequence looks something like this

- recursive_destroyer(node_1)
- Not null, call recursive_destroyer(node_1->next (node_2))
  - Not null, call recursive_destroyer(node_2->next (node_3))
    - Not null, call recursive_destroyer(node_3->next (null))
       - null, return
    - free(node_3), return
  - free(node_2), return
- free(node_1), return

The indentation shows the level of recursion. So if 2 lines have the same indentation then they are occurring in the same recursive call.

score 0 · Answer 2 · answered Oct 23 '20 at 19:18

Let's make a short example

 int f()
 {
     return 100;
 }
 
 int main()
 {
     int x, y;

     x = f();
     return f();
     y = f();
 }

x = f(); will save the context after f() finishes, the program will execute the next command, which is a return command.

Anything after the return command will not be executed. The recursion is similar, it will come back to the current node after it finishes processing the child node. You don't have a return command after the call, so it will resume the function until it get to ending curly brace.

How does this recursive delete node function work?

2 Answers2