Understanding function called by reference on lists

Question

I'd like to know why the code given below works well.

It should,recursively, given a list, put a -1 in front of the even numbers.

Ex. Input : 4->7->1->10->NULL Output : -1->10->1->7->-1->4->NULL

I don't understand how the function,being recursive, could keep track of the eventual *head,which is changed every time , due to the fact that the function called itself by reference.

In the end what I'm not getting is how the output could be correct given those (to me) misconception of how a recursive function by reference works.

Here's the code with the following declarations :

typedef struct El {
    int info;
    struct El *next;}ElementoLista;
typedef ElementoLista *ListaDiElementi;

void inserisci(ListaDiElementi *head) { 
    if((*head) != NULL && ((*head)->info)%2 == 0) {
        inserisci(&(*head)->next);
        ListaDiElementi aux = malloc(sizeof(ElementoLista));
        aux->info = -1;
        aux->next = *head;
        *head = aux;
    } else {    
        if((*head) != NULL) {               
            inserisci(&(*head)->next); 
        }  
    }  
}

i do not see any functions called "by reference (whatever it means)". Just the recursion — 0___________, Jan 27 '19 at 10:56
Your example seem strange. It's not just inserting "-1" in front but also do some reversing. Please clarify. And running the program does **not** give "-1->10->1->7->-1->4->NULL" but instead gives "-1->4->7->1->-1->10->NULL" — Support Ukraine, Jan 27 '19 at 11:00
@jacopoburelli it is normal function call with the pointer as parameter. — 0___________, Jan 27 '19 at 11:15
@P__J__ Okay,but why the *head doesn't change 'pointing location' so that i do not lose the list ? — jacopoburelli, Jan 27 '19 at 11:19
@jacopoburelli No way. The output is: "-1 -> 4 -> 7 -> 1 -> -1 -> 10 -> NULL" just check here: https://ideone.com/VByErh If you get another output you are printing the list in a wrong way. Post all your code... how do you construct the list. How do you print it? — Support Ukraine, Jan 27 '19 at 11:27
@jacopoburelli "List is created on top" top? top of what? I don't understand what you mean! — Support Ukraine, Jan 27 '19 at 11:36
Anyway - what you seem to miss is that `head` is always the address of the `next` pointer of the previous node. Consequently `*head` is the `next` pointer of the previous node and `(*head)->X` will access the current node. Each recursive call gets a new `head` (which is of cause restored when the recursive call returns). — Support Ukraine, Jan 27 '19 at 11:47
@4386427 Well your comment `Rule 1: Don't typedef pointers... ` is online. But I don't see any example. So why is that a rule? Do you have any other rules? — harper, Jan 27 '19 at 12:00
@harper I'm unsure what you are referring to in your last comment. Is it the rule "Don't typedef pointers" or is it the actual output of the code? Regarding the output you can find the example here https://ideone.com/VByErh showing that the code does **not** produce the output OP says. Then you ask: "Do you have any other rules?" oh yes - too many to give here but the main rule is "Keep it simple" so that code is easy to read, understand and maintain... and typedef of pointers violates that rule. — Support Ukraine, Jan 27 '19 at 12:12
@4386427 I overlooked your second comment, so I only referenced that funny rule about pointer typedefs. I found some other point (https://stackoverflow.com/questions/54284358/creating-a-pointer-directly-from-a-typedef-struct-definition/54284424#54284424) where you can read something similar. But there's no hint for the reason, why do you think so about pointer typedefs. — harper, Jan 27 '19 at 12:28
@harper The short explanation is that reading code with typedef'ed pointer is hard because you can't directly see that the variables are actually pointers. This is especially difficult if the type name does not mention "pointer" in some way. Example `typedef int* foo;` and then 200 lines later `void bar(foo x){…};` — Support Ukraine, Jan 27 '19 at 12:51

score 1 · Accepted Answer · answered Jan 27 '19 at 12:48

I think your troubles with the code is due to the code being "a bit poorly" written, i.e. less clear than it could be. I see three issues.

1) "typedef of pointer" makes it hard to understand what types are involved. Especially when it's not clear that a specific type is a pointer. A name like ListaDiElementi is not (at least not to me) making it clear that this is a pointer. A better name could be ElementoLista_ptr but overall it's better to avoid pointer typedef.

2) The function argument is named head. This is confusing because we normally think of head as the pointer to the first element of a list. But that's not what is going on here. The argument is really a double pointer and further it does not point to the first element. It points to next pointers.

3) The if constructs hides logic of the program.

So let's rewrite the code to get rid of the above while still keeping the same functionality:

typedef struct El {
    int info;
    struct El *next;
} ElementoLista;

void inserisci(ElementoLista **pNext) { 
    if ((*pNext) == NULL) return;

    inserisci(&(*pNext)->next);

    if(((*pNext)->info)%2 == 0) {
        ElementoLista* aux = malloc(sizeof(ElementoLista));
        aux->info = -1;
        aux->next = *pNext;
        *pNext = aux;
    }  
}

With this code it's easier to see that the code keeps calling it self recursively until it reaches the end. On the way back, i.e. as the function calls return, the code checks whether it needs to insert a "-1" node.

The same code with some comments to explain:

typedef struct El {
    int info;
    struct El *next;} ElementoLista;

// pNext is a pointer to the "next pointer" of the previous node
// Consequently (*pNext) is a pointer to the current node
void inserisci(ElementoLista **pNext) { 
    // Return if we have reached the end of the list
    if ((*pNext) == NULL) return;

    // Keep calling until the end is reached
    inserisci(&(*pNext)->next);

    // On the "way back" (i.e. as the recursive calls return) check
    // if we need to insert a "-1" node
    if(((*pNext)->info)%2 == 0) {
        // We need a new node
        ElementoLista* aux = malloc(sizeof(ElementoLista));
        aux->info = -1;

        // Make the new node point to current node
        aux->next = *pNext;

        // Update the next pointer to point to the new node
        *pNext = aux;
    }  
}

When you understand this simplified version of the code, you should also understand the original version.

Understanding function called by reference on lists

1 Answers1