Thread: Reversal of Doubly Linked List using Recursion !!

Hi,

I am trying to reverse a Linked list using recursion but whenever I try to print it after reversal it prints only the last element of the list.

Code:

void reverseRecursive(Node **root, Node *temp)
{
	Node *next = temp->next;
	if(temp->next == NULL)
		{
			*root = temp;
			return;
		}
	reverseRecursive(&(*root), temp->next);
//	printf("%d ", next->data);
	temp->next = temp->prev;
	temp->prev = next;	
}

Could you help me figure where the mistake lies?

I have just posted the reverse function to enable easy readability rather than post the entire code

Sorry, for assuming. I am attaching the smallest possible executable code

Code:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    Node *next;
    Node *prev;
}Node;
Node * createNode(int data)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}
void BuildList(Node **root, int data)
{
    Node *temp = *root;
    if(temp ==NULL)
        {
            *root = createNode(data);
        }
    else
    {
        while(temp->next != NULL)
        {
            temp = temp->next;
        }
        Node *newNode = createNode(data);
        temp->next = newNode;
        newNode->prev = temp;
    }
}


void printList(Node **root)
{
    Node *temp = *root;
    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
void reverseRecursive(Node **root, Node *temp)
{
    Node *next = temp->next;
    if(temp->next == NULL)
        {
            *root = temp;
            return;
        }
    reverseRecursive(&(*root), temp->next);
//    printf("%d ", next->data);
    temp->next = temp->prev;
    temp->prev = next;    
}


int main()
{
    Node *root = NULL;
    BuildList(&root, 67);
    BuildList(&root, 68);
    BuildList(&root, 69);
    BuildList(&root, 70);
//    printList(&root);
//    reverseIterative(&root);
//    printList(&root);
    reverseRecursive(&root, root);
    printList(&root);
//    printRecursive(root);
    return 0;
}

Fundamentally, isn't it bad to use recursion in this instance? Maybe you won't encounter it in the wild but it seems like the number of function calls you'd have to make would grow with the size of the list which means you're vulnerable to overflows. Why not an iterative method? I think recursion is best left for when you know the maximum depth ahead of time.

Originally Posted by MutantJohn

Fundamentally, isn't it bad to use recursion in this instance? Maybe you won't encounter it in the wild but it seems like the number of function calls you'd have to make would grow with the size of the list which means you're vulnerable to overflows. Why not an iterative method? I think recursion is best left for when you know the maximum depth ahead of time.

I know it is better to use iterative method, but I wanted to try it with recursion too. Just to learn

Thanks.

Originally Posted by AndrewHunter

In order to change the values actually at temp, just like for root, you need a pointer to a pointer. Not just a pointer.

Okay, I think I get it. temp is just a local variable whose actual values do not get modified. So, I'd have to pass the address of the exact location of the node in the heap. Right?