Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Why is the recursion depth in the algorithm so large? C++

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

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading