Linked list recursion..Why do I need return statement?

void add(llist *list, lnode *newNode){
    list->size++;
    addRecursion(&list->head, newNode);
}

lnode* addRecursion(lnode **node, lnod开发者_开发百科e *newNode){
    if(*node == NULL){
        *node = newNode;
    }
    else{
        lnode *nextNode = (*node)->next;
        (*node)->next = addRecursion(&nextNode, newNode);

    }
    return *node;
}

This code works fine.. I took a look at the codes online and made a few changes. But I still don't understand that why addRecursion function has to have the return type. I changed the function like

void addRecursion(lnode **node, lnode *newNode){
        if(*node == NULL){
            *node = newNode;
        }
        else{
            lnode *nextNode = (*node)->next;
            addRecursion(&nextNode, newNode);

        }
    }

then it didn't work..

It always returns the value it stores into *node, and in your modified code it loses that value since the recursive call passes a local temp rather than the place it actually needs to put the value, and then does the store after it returns. A very odd construct. You can make addRecursion void (and simpler) if you just get rid of that local var:

void addRecursion(lnode **node, lnode *newNode){
    if(*node == NULL){
        *node = newNode;
    }else{
        addRecursion(&(*node)->next, newNode);
    }
}

To assign something to (*node)->next. That points to the next node of the list, I suppose. So without that assignment, the list does not go to the last node, to which the new node is to be added. Recursion could be replaced with iteration.

Because the function is returning the address of the next node which is required in your algorithm to set the final node.

It might help to visualize the call stack growing/shrinking as the recursion progresses. Assume the following list:

node1 -> node2 -> node3 -> null

Then addRecursion unfolds as follows (psuedocode):

addRecursion(&node1, newNode)
    node1.next = addRecursion(&node2, newNode);
        node2.next = addRecursion(&node3, newNode);
            node3.next = addRecursion(null, newNode); // returns &newNode
            node3.next = &newNode;
        node2.next = &node3;
    node1.next = &node2;
// return value ignored

The new node is added to the end and each link in the chain is preserved.

It should also work if you make this adjustment to your code where you re-assign the value of nextNode back to (*node)->next since you passed that value by reference to the recursive function call (and therefore it was modified during the later recursive calls):

void addRecursion(lnode **node, lnode *newNode)
{
    if(*node == NULL)
    {
        *node = newNode;
        return;
    }

    lnode *nextNode = (*node)->next;
    addRecursion(&nextNode, newNode);
    (*node)->next = nextNode; //Add this line to re-connect the link
}

Chris's version above is a bit cleaner though since it axes out two assignments and in doing so also saves some space on the stack since there is no storage required for the local pointer variable nextNode.