Jun 132012
 

Write a recursive function to print the Linked list in reverse order …

Assume the below definition of Node of a Linked List

struct Node{
    int data;
    struct Node * link;
};

The function should accept pointer to the first Node of the list and should have the below signature:

/* Print the linked list in backward order (reverse) */
void printBack(struct Node* head);

Solution:

    void printBack (struct Node* head)
    {
        //terminating condition
        if(head == NULL)
            return;

        // Print the list and then print the Node
        printBack (head->next); 
        printf("%d ", head->data);

    }

This is an example of Head Recursion. In Head recursion the recursive function is called first and then perform the operation.

Tail recursion is the case when we perform the operation first and then call the recursive function. For example, if we want to print the list in forward order, then we can use tail recursion as below:

    void printForward(struct Node* head)
    {
        //terminating condition
        if(head == NULL)
            return;    

        printf("%d ", head->data);
        printForward (head->next);
    }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)