Recursion causing program to crash but same concept in while loop does not from C++ destructors

Question

I'm creating a linked list class and the deletion of the linked list has been causing my program to crash but I can't understand why even though I've traced it line by line in debug mode.

In the main method I create the list and instantiate values:

List list = List(new Node(rand()));
while (list.size < 10000)
{
    list.add(rand());
}

The list takes in a Node pointer and assigns in to a member Node pointer called head. The node also has another member variable which is an integer called size.

Then at the end of the method the destructor for list is called:

~List()
{
    delete head;
}

and that destuctor is calling the destructor for the head node which is:

~Node()
{
    delete next;
}

Each node has a Node pointer called next that points to either the next node in the list or nullptr if it's the end which terminates the delete calls.

What confuses me the most is that this does work for all values under 2000, however, at some point in the 2000's, it causes the program to crash.

When I left the Node destructor empty and changed the List destructor to be:

~List()
{
    while (head)
    {
        Node* temp = head->next;
        std::cout << head->value << std::endl;
        delete head;
        head = temp;
    }
    size = 0;
}

The program was working and it was getting rid of all nodes within the linked list. As far as I can tell, I am applying the same principle so the recursive call so I don't know what's causing the crash.

Node struct:

int value;
Node* next;

Node(int val, Node* node = nullptr)
{
    value = val;
    next = node;
}
~Node()
{
    //delete next;
}

List struct:

Node* head;
int size;

List(Node* val)
{
    head = val;
    size = 1;
}
~List()
{
    //delete head;
    while (head)
    {
        Node* temp = head->next;
        std::cout << head->value << std::endl;
        delete head;
        head = temp;
    }
    size = 0;
}
void add(int value)
{
    head = new Node(value, head);
    size++;
}

What usually crashes recursive calls above some arbitrary number? — Rotem
Recursion uses memory in the stack for each function call's data. Eventually, if you create enough function calls, the call stack runs out of memory and you have a Stack Overflow. Just write it iteratively. — ggorlen
I don't know what's causing the crash -- Most runtimes will tell you in the crash error message that you have a stack overflow. — PaulMcKenzie
Recursive destructors for a linked list is never a good idea, especially for large lists. Always use an iterative loop instead. — Remy Lebeau
This is can also occur in non-recursive function calls. It just means too many function calls using too much (non dynamic) data. In recursion it happens more frequently. — engf-010

Jarod42 Jarod42 · Accepted Answer · 2019-10-09T09:48:54

The program is correct and not ill-formed.

The issue comes from memory limitation.

One "workaround" is to handle memory manually with iteration.

Recursion causing program to crash but same concept in while loop does not from C++ destructors

1 Answers