stack overflow during recursion in C++

Question

I wrote a template class for Singly linked list. For printing values in reverse order, I implemented traverse_reverse() function using recursion. When the number of elements in list reaches near 4000, calling this function threw stack overflow error. At such range of numbers, I am not sure if stack overflow should happen.

Environment is Visual Studio 2019 Community edition, Windows 10 64 bit OS.

My questions are:

1. How can I avoid stack overflow

2. How can I increase the size of stack at runtime.

Below is the code snippet:

#pragma once
#include <mutex>
#include <iostream>

namespace MyDS
{
    template <typename T>
    struct Node
    {
        T* m_pData = nullptr;
        Node* m_pNext = nullptr;
    };

    template <class T>
    class sList
    {
        Node<T>* m_pHead = nullptr;
        Node<T>* m_pCurrentNode = nullptr;
        int m_Size = 0;
        std::mutex m_ListMutex;

    public:
        bool insert_front(T val);
        bool insert_last(T val);
        bool insert_anywhere(T val, int loc);

        bool remove(T val);
        //bool remove(int loc);
        bool remove_front();
        bool remove_last();

        void traverse();
        void traverse_reverse();

        bool emptyList();

        int getSize();

    private:
        void traverse_reverse(Node<T>* pNode);
    };

    template<typename T>
    void sList<T>::traverse_reverse(Node<T>* pNode)
    {
        if (pNode->m_pNext != nullptr)
            traverse_reverse(pNode->m_pNext);
        std::cout << *pNode->m_pData << " ";
    }

    template<typename T>
    bool sList<T>::emptyList()
    {
        bool ret = false;
        if (getSize() > 0)
        {
            std::lock_guard<std::mutex> lg(m_ListMutex);

            Node<T>* pTempNode = m_pHead, pTempNode1 = nullptr;
            while (pTempNode->m_pNext!= nullptr)
            {
                pTempNode1 = pTempNode->m_pNext;

                delete pTempNode->m_pData;
                delete pTempNode;
                pTempNode = pTempNode1;
            }

            delete pTempNode->m_pData;
            delete pTempNode;

            pTempNode->m_pData = pTempNode1->m_pData = m_pHead->m_pData = m_pCurrentNode->m_pData = nullptr;
            pTempNode = pTempNode1 = m_pHead = m_pCurrentNode = nullptr;
            m_Size = 0;
        }

        ret = true;
        return ret;
    }

    template<typename T>
    int sList<T>::getSize()
    {
        return m_Size;
    }

    template<typename T>
    bool sList<T>::insert_front(T val)
    {
        Node<T>* pNode = new Node<T>;
        pNode->m_pData = new T(val);

        if (getSize() > 0)
        {
            pNode->m_pNext = m_pHead;
        }

        m_pHead = pNode;
        m_Size++;

        return true;
    }


    template<typename T>
    bool sList<T>::insert_last(T val)
    {
        Node<T>* plastNode = m_pHead;
        while (plastNode->m_pNext!= nullptr)
            plastNode = plastNode->m_pNext;

        plastNode->m_pNext = new Node<T>;
        plastNode->m_pNext->m_pData = new T(val);

        return true;
    }


    template<typename T>
    bool sList<T>::insert_anywhere(T val, int loc)
    {
        return true;
    }


    //template<typename T>
    //bool sList<T>::remove(int loc)
    //{
    //  return true;
    //}


    template<typename T>
    bool sList<T>::remove_front()
    {
        std::lock_guard<std::mutex> lg(m_ListMutex);
        Node<T>* pNode = m_pHead;
        m_pHead = m_pHead->m_pNext;

        delete pNode->m_pData;
        delete pNode;

        m_Size--;
        return true;
    }

    template<typename T>
    bool sList<T>::remove_last()
    {
        Node<T>* plastNode = m_pHead;
        std::lock_guard<std::mutex> lg(m_ListMutex);
        if (getSize() > 1)
        {
            while (plastNode->m_pNext->m_pNext != nullptr)
                plastNode = plastNode->m_pNext;

            Node<T>* pNode = plastNode->m_pNext;
            plastNode->m_pNext = nullptr;

            delete pNode->m_pData;
            delete pNode;
            pNode->m_pData = pNode = nullptr;
            m_Size--;
        }
        else if(getSize() == 1) // Only 1 node 
        {
            delete m_pHead->m_pData;
            delete m_pHead;

            m_pHead->m_pData = m_pHead = nullptr;
            m_Size--;
        }
        else   // No node available
        {
            //Nothing to do 
        }

        return true;

    }

    template<typename T>
    bool sList<T>::remove(T val)
    {
        bool ret = false;
        Node<T>* pNode = m_pHead;
        Node<T>* pNodeNext = pNode->m_pNext;

        if (pNode->m_pData == val)
        {
            ret = remove_front();
        }
        else if (pNodeNext->m_pData == val)
        {
            pNode->m_pNext = pNodeNext->m_pNext;
            pNodeNext->m_pNext = nullptr;

            delete pNodeNext->m_pData;
            delete pNodeNext;
            pNodeNext->m_pData = pNodeNext = nullptr;
            ret = true;
            m_Size--;
        }
        else
        {
            while (pNodeNext->m_pData != val)
            {
                pNode = pNodeNext;
                pNodeNext = pNodeNext->m_pNext;
            }

            if (pNodeNext == nullptr)
                ret = false;
            else
            {
                pNode->m_pNext = pNodeNext->m_pNext;
                pNodeNext->m_pNext = nullptr;

                delete pNodeNext->m_pData;
                delete pNodeNext;
                pNodeNext->m_pData = pNodeNext = nullptr;
                m_Size--;
                ret = true;
            }
        }

        return ret;
    }

    template<typename T>
    void sList<T>::traverse()
    {
        m_pCurrentNode = m_pHead;
        while (m_pCurrentNode->m_pNext != nullptr)
        {
            std::cout << *m_pCurrentNode->m_pData<<" ";
            m_pCurrentNode = m_pCurrentNode->m_pNext;
        }

        std::cout << *m_pCurrentNode->m_pData;
        std::cout << std::endl;
    }

    template<typename T>
    void sList<T>::traverse_reverse()
    {
        m_pCurrentNode = m_pHead;
        traverse_reverse(m_pCurrentNode);
        std::cout << std::endl;
    }

}

#include "MyDS.h"

int main()
{
    MyDS::sList<int> myList;
    for(int i = 0; i <= 3987; ++i)
        myList.insert_front(i);

    myList.traverse_reverse(); //Recursion

//  myList.traverse();
    return 0;
}

Answer 1

As the other answers have pointed out, you have not provided the full code. That said, guessing from the code you have given, I believe that the issue is that you are right about the stack overflow occurring due to too many function calls on the stack when the list of elements is sufficiently long.

In general, it is best to avoid having lots and lots of function calls on the stack. Increasing the stack size is most often not a good solution. See for instance why is stack memory size so limited? for some discussions on this topic.

A single-linked list might be difficult reg. this. One option might be to reverse the single-linked list (maybe creating a new single-linked list), and then just traversing that one (possibly deleting the created list afterwards). A double-linked list would be able to do it very easily and efficiently, since you can just find the last element and then go backwards from there.

Answer 2

If you want to avoid stack overflow, don't use recursion. a simple while can do same job without requiring further resources from stack:

template<typename T>
void sList<T>::traverse_reverse(Node<T>* pNode)
{
    while (pNode != nullptr){
        std::cout << *pNode->m_pData << " ";
        pNode=pNode->m_pNext;
    }
}  

To increase stack size: Increase stack size in c++

However, in case the above code does not work, I suspect your problem is elsewhere. my initial guess is that you have an infinite loop (in recursion). Let's say for some reason, you have circular dependencies in your list: every node has his m_pNext filled with something other then nullptr. Recursion will never end, hence stackoverflow error. The code above will not work.

Usually circular dependencies arise from incorrect implementation of insert or remove methods. If for some reason you update your pointer in removal incorrectly to another node, it can cause circular dependency.

You can use following code to check for circular dependencies:

template<typename T>
void sList<T>::traverse_reverse(Node<T>* pNode)
{
    Node<T>* org_p=pNode;
    while (pNode->m_pNext != nullptr){
        pNode=pNode->m_pNext;
        if(org_p==pNode){
            std::cout << "Circular Dependency";
            break;            
        }
    }
    std::cout << "No Circular Dependency";
}  

Answer 3

For printing values in reverse order, I implemented traverse_reverse() function using recursion.

Recursion (unless optimized by your compiler as tail-recursive calls) always consume call stack space. See also this draft report for examples of interesting GCC optimizations. Probably, your C++ compiler is capable of doing similar optimizations.

You could instead prefer consuming heap space, e.g. use intermediate standard C++ containers to keep temporary data.

You could be interested by continuation-passing style. Sometimes it enables you to avoid recursion (and use more heap memory instead).

You can find C++ implementations (recent GCC or Clang comes to mind...) whose source code of std::vector or std::list is open source and readable. You might be surprised by their complexity, related to the rule of five.

If you compiled your C++ code with a recent GCC, you could have used g++ -Wall -Wextra -g -fstack-protector -Wstack-usage=2048 perhaps combined with -O2 to be warned of large call frames.

You might be interested in static source program analysis tools such as Frama-C++, Coverity, Clang static analyzer, or the address sanitizer, or in writing your own GCC plugin to build a call graph and sometimes detect potential stack overflows (but be aware of Rice's theorem). See also valgrind.