CODEWITHSUNDEEP
crecursionlinked-list
codereviewanskquestions
codereviewanskquestions

Reputation: 13998

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, lnode *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..

Upvotes: 1

Views: 230

Answers (5)

Jason
Jason

Reputation: 32540

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.

Upvotes: 0

Chris Dodd
Chris Dodd

Reputation: 126418

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);
    }
}

Upvotes: 2

Wayne
Wayne

Reputation: 60424

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.

Upvotes: 1

Argote
Argote

Reputation: 2155

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

Upvotes: 1

vpit3833
vpit3833

Reputation: 7961

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.

Upvotes: 1

Related Questions