How does recursion work when inserting nodes in linked lists?

Question

I have trouble understanding how these functions work:

Answer 1

It would be better if you post the whole code here, instead of just posting a part of it.

In order to understand the insertion of a node in the list, first you should try to understand - What fold() function is doing?

The definition of recursive function fold():

void *fold(void (*func)(void *, Node *), void *accum, Node *head) {
  if (head == NULL) {
    return accum;
  } else {
    func(accum, head);
    return fold(func, accum, head->next);
  }
}

First understand the parameters of fold() function:

• void (*func)(void *, Node *) : a function pointer which can point to any function which takes two parameter - first is of type void * and second is of type Node * and returns nothing.
• void *accum : accum is a pointer to void type, aka generic pointer which can be converted to any other pointer type.
• Node *head : head is a pointer to Node type.

Now, let's decode the fold() function definition:

      if (head == NULL) {
          return accum;
      .....
      .....

This is the terminating condition of recursion - When head is NULL return accum (which is a void pointer).

If head is not NULL then

  } else {
    func(accum, head);
    .....
    .....

call func(accum, head), which means call the function which has been passed to fold() as first argument and pass accum and head as its arguments.

In the insert(), calling fold() as -

fold(tail, &ptr, *head);

• tail() : a function
• &ptr : Address of a pointer to pointer to Node type
• *head : head pointer of list

Now check the tail() definition -

static void tail(void *accum, Node *node) {
  *(Node ***)accum = &(node->next);
}

Since, first argument accum is void pointer to which &ptr is passed and we know that ptr contain the address of Node ** type. So we can cast the accum with (Node ***) and dereferencing it will give of Node ** pointer. The type of node->next is struct node * and Node is alias of struct node which means node->next is of type Node * and its address is of type Node **. So, we can assign &(node->next) to accum. After assignment, the accum will contains the address of next pointer of node passed to tail().

After calling func(), the fold() call itself (recursive call):

    return fold(func, accum, head->next);
 }
}

Note that now the accum contains the address of next pointer of currently processing node of the list and passing head->next means the recursive call will process the next node of list and this recursive call assign the address of next of node passed to accum pointer. With this much of understanding, now I can say, this recursive call will end up assigning the address of next of last node of list to accum.

When this recursion wind-up and returned to insert(), the ptr will have the address of next of last node of list. After fold() call, we have following in insert():

*ptr = new;

i.e. assigning the new node to next pointer of last node which means inserting the newly created node to the last of list.

On similar lines, try to decode the map function and other part of program.