Why does theis recursive function not work?

Question

I am trying to write a recursive function to reverse a doubly linked list. This code is not complete yet but I am hit with a issue. The application is not executing completely.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef struct nodes
{
    uint8_t x;
    struct nodes *next;
    struct nodes *prev;
}Node;

Node *head = NULL;

void rev_rec_dll(Node **a, Node **b)
{
        //check if it is last node in the list
    if((*a)->next != NULL)
    {
                //set next to prev and prev to next
        (*a)->next = (*a)->prev;
        (*a)->prev = (*b);
        printf("done for node %d and moving on..\n", ((*a)->x));
        //recursive call by passing next two nodes
                rev_rec_dll(b, &((*b)->next));
    }
    else
    {
        printf("reached new head\r\n");
        head = (*a);
    }
}

void add_node(Node **h_node, uint8_t x)
{
        //check if there is at least one node in the list and if not add first node
    if((*h_node) == NULL)
    {
        *h_node = (Node *)malloc(sizeof(Node));
        (*h_node)->x    = x;
        (*h_node)->next = NULL;
        (*h_node)->prev = NULL;
    }
    else
    {
        Node *temp = *h_node;
        //get the last node
        while(temp->next != NULL)
        {
            temp = temp->next;
        }
        //add new node
        Node *newNode = (Node *)malloc(sizeof(Node));
        
        newNode->x      = x;
        newNode->next   = NULL;
        newNode->prev   = temp;
        
        temp->next      = newNode;
    }
}

void display_nodes(Node *h_node)
{
    while(h_node != NULL)
    {
        printf("Node: %u\n", h_node->x);
        h_node = h_node->next;
    }
}

int main(int argc, char **argv)
{
        //add three nodes
    add_node(&head, 1);
    add_node(&head, 2);
    add_node(&head, 3);

    //display nodes
    display_nodes(head);

        //add three more nodes
    add_node(&head, 4);
    add_node(&head, 5);
    add_node(&head, 6);

        //display all 6 nodes
    display_nodes(head);
    
        //reverse the linked list
    rev_rec_dll(&head, &(head->next));

        //display reversed nodes 
    display_nodes(head);
    
    return 0;
}

The output of the program is given below:

Node: 1
Node: 2
Node: 3
Node: 1
Node: 2
Node: 3
Node: 4
Node: 5
Node: 6
done for node 1 and moving on..

I want to know what is wrong in the function rev_rec_dll(). Also, I want to know if the way I am passing the arguments to this function is correct or not. If it is not correct please provide appropriate reason on why it is wrong. The arguments passed to rev_rec_dll function is current node and next node in the linked list.

The reversing logic may not be accurate but I want to know if the way the arguments are passed is correct. Why does it exit in the middle? A memory violation?

Answer 1

For starters it is a bad idea to declare the pointer to head node as a file scope variable and when the functions depend on the file scope variable.

Node *head = NULL;

You should move this declaration inside the function main and correspondingly rewrite your functions.

Also the structure declaration will look better if to declare it like

typedef struct Node
{
    uint8_t x;
    struct Node *next;
    struct Node *prev;
} Node;

Otherwise the names nodes and Node will only confuse readers of the code.

There are two problems with the function. The first one is that initially the second function argument points to the data member next of the head node

rev_rec_dll(&head, &(head->next));

that is changed within the function in the compound statement of the if statement.

To make it clear consider a list that contains only two nodes

| NULL <- 1 -> 2 | <-> | 1 <- 2 -> NULL|

Inside the first recursive call of the function there are executed the following statements

    (*a)->next = (*a)->prev;
    (*a)->prev = (*b);

Again pay attention to that the function is called like

rev_rec_dll(&head, &(head->next));

That is the parameter b of the function points to the data member next of the head node and the first of the above statements changes the value of the data member

    (*a)->next = (*a)->prev;

So now the expression *b yields data member next that now contains the value of the data member prev (in this case NULL).

In fact you have

    (*a)->next = (*a)->prev;
    (*a)->prev = ( *a )->next; //(*b);

because the expressions ( *a )->next and *b are equivalent due to initializations of parameters by argument expressions.

That is the both data members. next and prev, get the initial value of the data member prev and you have

| NULL <- 1 -> NULL | <- | 1 <- 2 -> NULL|

Then the function is called like

rev_rec_dll(b, &((*b)->next));

that invokes undefined behavior because the expression *b yields a null pointer.

Another problem is that in this code snippet

else
{
    printf("reached new head\r\n");
    head = (*a);
}

data members prev and next of the last node in the list are not changed because the control is bypassed the compound statement of the if statement

And moreover your function will invoke undefined behavior if it will be called for an empty list.

The function should be declared with only one parameter like for example

void rev_rec_dll( Node **head );

Here is a demonstration program that shows how the recursive function that reverses the list can be implemented.

In the demonstration program there is not used a file scope pointer to the head node. In this case within a program you will be able to define multiple lists.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

typedef struct Node
{
    uint8_t x;
    struct Node *next;
    struct Node *prev;
} Node;

void clear( Node **head )
{
    while (*head)
    {
        Node *current = *head;
        *head = ( *head )->next;
        free( current );
    }
}

size_t assign( Node **head, const uint8_t *a, size_t n )
{
    clear( head );

    size_t cnt = 0;

    for ( Node *prev = NULL; n-- && ( *head = malloc( sizeof( Node ) ) ) != NULL; cnt++)
    {
        ( *head )->x = *a++;
        ( *head )->next = NULL;
        ( *head )->prev = prev;
        prev = *head;
        head = &( *head )->next;
    }

    return cnt;
}

void rev_rec_dll( Node **head )
{
    if ( *head )
    {
        Node *tmp = ( *head )->next;
        ( *head )->next = ( *head )->prev;
        ( *head )->prev = tmp;

        if (( *head )->prev != NULL)
        {
            *head = ( *head )->prev;
            rev_rec_dll( head );
        }
    }
}

void display_nodes( const Node *head )
{
    for (; head != NULL; head = head->next)
    {
        printf( "%" PRIu8 " -> ", head->x );
    }

    puts( "null" );
}

int main( void )
{
    Node *head = NULL;
    uint8_t a[] = { 1, 2, 3, 4, 5, 6 };

    assign( &head, a, sizeof( a ) / sizeof( *a ) );

    display_nodes( head );

    rev_rec_dll( &head );

    display_nodes( head );

    clear( &head );
}

The program output is

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

Answer 2

There's no real point of using pointer to a pointer in rev_rec_dll(Node **a, Node **b), i would suggest you read into practical implications of pointers to pointers

What you can do here is just use regular pointers like so:

void rev_rec_dll(Node* a, Node* b)
{
    //check if it is last node in the list
    if(a->next != NULL)
    {
        //set next to prev and prev to next
        a->next = a->prev;
        a->prev = b;
        printf("done for node %d and moving on..\n", a->x);
        //recursive call by passing next two nodes
        rev_rec_dll(b, b->next);
    }
    else
    {
        printf("reached new head\r\n");
        head = a;
    }
}

then in main function call it like so

rev_rec_dll(head, head->next);

also, as Vlad mentioned you shouldn't use two parameters in this function, it adds unnecessary complexity as well as makes it a bit harder to track if you pass and use NULL in the future.

also also, it's best that you learn how to use debugger now to see where things hit the fan clearly.