Code for recursively filling in a unidirectional list:

#include <iostream>
#include <random>

using namespace std;

class Queue
{
private:
    class Node;

public:
    Queue()
    {
        size = 0;
        head = nullptr;
    }

    Node* push_back(int data, Node* next)
    {
        static int depth; // recursion depth

        if (next == nullptr)
        {
            next = new Node(data);
            if (size == 0)
                head = next;
            size++;
            return next;
        }
        
        depth++; // recursion depth

        next->pNext = push_back(data, next->pNext);
        return next;
    }
        Node* get_head() { return head; }
    int get_size() { return size; }

private:
    class Node
    {
    public:
        Node* pNext;
        int data;

        Node(int data = int(), Node* pNext = nullptr)
        {
            this->data = data;
            this->pNext = pNext;
        }
    };

    int size;
    Node* head;
};

Explain why the recursion depth when filling the list through a loop is equal to (n^2 – n) / 2, instead of n?
Because of this, stack overflow occurs when the number of elements is greater than 3195

>Solution :

It’s because nothing resets depth to zero, before each new value gets inserted.

So, when the 2nd value gets pushed into the linked list, depth gets incremented for the first time, from 0 to 1. When the 3rd value gets inserted into the linked list, depth then gets incremented from 1 to 2, then to 3. And so on.

You end up counting not just the recursion depth of the last insertion operation, but the sum total of all insertion operations.