CODEWITHSUNDEEP
c++recursiondata-structures
user3467152
user3467152

Reputation: 343

How to write a method definition for a recursive function?

I have a homework question that said:

Destructor_Helper is a recursive function that deallocates each node of singly linked list. Write a method definition for destructor_helper.

 struct Node
 {
      string data;
      Node *next;
 }

 void List::~List()  {
     destructor_helper(head);
 }

My answer was:

     void Destructor_Helper(Node *n) {
     cout<< n->data << endl;
     if (n->next != NULL)
          Destructor_Helper(n->next);
 }

My answer was counted wrong, would someone help me out to figure out the problem.

Upvotes: 2

Views: 99

Answers (2)

TobiMcNamobi
TobiMcNamobi

Reputation: 4813

** SPOILER **

void Destructor_Helper(Node *n) {
    cout<< n->data << endl;
    if (n->next != NULL)
    {
        Destructor_Helper(n->next);
    }
    delete n;
}

Should do the trick.

Upvotes: 1

Shoe
Shoe

Reputation: 76240

You are answer was counted wrong because you are not doing any deallocation.

To deallocate a linked list you can store the next node, deallocate the current and then go recursively on the next node. I would go like this:

void destructor_helper(Node *n) {
    if (n == NULL) return;
    Node* next = n->next;
    delete n;
    destructor_helper(next);
}

You can easily spot the base case of the recursion, which is when the current node is NULL. At that point we just need to return. Then, we store the next node in a local variable called next and we delete the current. The next local variable can be NULL, it doesn't matter. Then we pass next recursively to get the rest of the list deleted.

Upvotes: 5

Related Questions