PSET5 Unload() recursive sub-function causes 112 bytes to leak - why?

Question

I've already fixed this issue playing around with my code, but I cannot seem to understand why this (former) version of my recursive function leaks 112 bytes (2 nodes).

Can anyone please help me understand?

Thanks!

void kill(node *n)
// Deletes the list that *n points to 
if(n  == NULL)
{
  free(n);
}
else
{
kill(n->next);
}

This is the new (fixed) version:

void kill(node *n)
{
if(n != NULL)
{
    kill(n->next);
}
free(n);
}

Answer 1

Actually, it probably leaks a lot more than that, depending on the size of the linked list.

The first version is an either/or. It will either free a node or move to the next node. In practice, that means that it will walk the linked list to the last node and free it, and then return to the original calling code.

The second version is different. It will hit the if condition and recursively call itself until it gets to the last node that is null. Then, the code drops past the if statement to the free call. It frees the null node (essentially a do-nothing, which is fine), returns to the previous recursion, repeats the process of deleting that node (which now has no children), returns to the next previous node, frees that node, etc., until it gets back to the original calling function.

That's how a good recursion will work.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)