How can I prevent StackOverflowException in my code

Question

In my code, I cannot figure out why I keep getting 'Process is terminating due to StackOverflowException.' only on the second output.

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace _2018JuniorQ5
{
    class Program
    {
        //Variable Decleration
        public static int pages = 0;
        public static string[] bookFormat;
        public static List<string> alreadyChecked = new List<string>();
        public static List<string> nodesToCheck = new List<string>();
        public static int level = 0;
        public static List<string> childrenNodes = new List<string>();
        public static void Main(string[] args)
        {
            //Get input
            pages = Convert.ToInt32(Console.ReadLine());
            bookFormat = new string[pages];
            for (int x=0; x<pages; x++)
            {
                bookFormat[x] = Console.ReadLine();
            }        
            //Display if all pages are reachable
            Console.WriteLine(getReachablePages(1));
            //Find shortest path
            List<string> NodeBegin = new List<string>();
            NodeBegin.Add("1");
            Console.WriteLine(getShortestPath(NodeBegin));            
        }
        public static string getReachablePages(int pageToCheck)
        {
            string[] options=(bookFormat[pageToCheck - 1]).Split(' ');
            alreadyChecked.Add(Convert.ToString(pageToCheck));
            for (int a=1; a<=Convert.ToInt32(options[0]); a++)
            {
                if (!alreadyChecked.Contains(options[a]))
                {
                    getReachablePages(Convert.ToInt32(options[a]));
                }       
            }
            if (alreadyChecked.Count == pages)
            {
                return "Y";               
            }
            else
            {
                return "N";
            }
            alreadyChecked.Clear();  
        }
        public static int getShortestPath(List<string> nodesToCheck)
        {
            level++;
            childrenNodes.Clear();
            for (int q = 0; q < nodesToCheck.Count; q++)
            {
                string[] options = bookFormat[Convert.ToInt32(nodesToCheck[q])-1].Split(' ');                
                if (options[0] == "0")
                {
                    return level;
                }
                else
                {
                    for (int t = 1; t < options.Length; t++)
                    {
                        if (!alreadyChecked.Contains(options[t]))
                        {
                            childrenNodes.Add(options[t]);
                            alreadyChecked.Add(nodesToCheck[q]);
                        }
                    }
                }
                nodesToCheck.Clear();
            }
            return getShortestPath(childrenNodes);
        }
    }
}

The first output from the getReachablePages method works, and does not give any errors. However, the second output from the getShortestPath gives the "Process is terminating due to StackOverflowException" error. Can someone explain why the getReachablePages method works, but the getShortestPath method doesn't work?

Answer 1

The problem at the moment is that List<string> is a reference type, so when you pass childrenNodes to getShortestPath (getShortestPath(childrenNodes)), you're actually passing a reference to the same list in memory.

The next thing you do is call childrenNodes.Clear(), which empties that list. Because nodesToCheck and childrenNodes are both pointing at the same list, calling childrenNodes.Clear() means that you have no nodes to check.

Why does this cause a StackOverflowException? It causes one because you have no exit condition for when nodesToCheck is empty. You just keep calling the same method over and over.

I propose the following solution:

public static int getShortestPath(List<string> nodesToCheck)
{
    if (!nodesToCheck.Any())
    {
        return -1;
    }

    var childrenNodes = new List<string>();
    level++;
    for (int q = 0; q < nodesToCheck.Count; q++)
    {
        string[] options = bookFormat[Convert.ToInt32(nodesToCheck[q])-1].Split(' ');                
        if (options[0] == "0")
        {
            return level;
        }
        else
        {
            for (int t = 1; t < options.Length; t++)
            {
                if (!alreadyChecked.Contains(options[t]))
                {
                    childrenNodes.Add(options[t]);
                    alreadyChecked.Add(nodesToCheck[q]);
                }
            }
        }
        nodesToCheck.Clear();
    }
    return getShortestPath(childrenNodes);
}

• When nodesToCheck is empty, return -1 (i.e. no path).
• Create a new List<string> for childrenNodes within the getShortestPath method.

While this should fix your problem, I would recommend making your entire method self-contained. It's essentially a stateless method, but you're maintaining state outside the method, which led to the problem you have seen, and could lead to more problems if you call this method in a multi-threaded environment.

The other odd thing I noticed, is that you're looping through nodesToCheck, but the way your code is written means that you will only ever consider the first node because you clear nodesToCheck at the end of the first iteration, leaving the list empty. Further more, you're adding nodesToCheck[q] to alreadChecked once per item in options, which I'm sure can't be right.

I recommend learning to use the debugger in Visual Studio. The debugger allows you to step through your code line-by-line, inspect variables, etc. - this will help you locate problems in your code.

P.S. While it is not the correct solution to your problem, if you wish to copy a list you can use LINQ's ToList() method: var listB = listA.ToList();