Possible Reasons for Stack Overflow

Question

I have the following C# code which fills an ArrayList with Random numbers between 1 to 30. I have to call this function 25 times. My code:

    private void getNextTrack()
    {
        int currentTrack = new Random().Next(1, 30);
        if (playlist.Contains(currentTrack) || (topicNo == 8 && currentTrack == 29) || (topicNo == 3 && currentTrack == 14))
            getNextTrack(); //If track already exsits or the 2 specified topics dont have that track no. then try again.

        else
        {
            playlist.Add(currentTrack);
            ++tracksPlayed;
        }
    }

This works well when the function is called initial 10-11 times but after that it immediately gives a stack overflow exception and stops. I am not understanding why as the recursion is not infinite.

Answer 1

This happens because of the following scenario:

1. You generate a random number
2. Suppose none of the conditions in the first if is met, else clause is executed
3. currentTrack is added to the playlist
4. You call the function more times, which results in almost all numbers from range [1, 30] being used
5. This increases the chance of the first condition being met
6. Which makes possible that for many successive, recursive calls of getNextTrack the track already exists.
7. Which may result in stack overflow.

Note that the numbers will be repeated most of the time, because you keep using a new random generator. The documentation of Random constructor says:

The default seed value is derived from the system clock and has finite resolution. As a result, different Random objects that are created in close succession by a call to the default constructor will have identical default seed values and, therefore, will produce identical sets of random numbers. This problem can be avoided by using a single Random object to generate all random numbers. You can also work around it by modifying the seed value returned by the system clock and then explicitly providing this new seed value to the Random(Int32) constructor. For more information, see the Random(Int32) constructor.

^{(emphasis mine)}

The recursion necessary for a stack overflow to occur doesn't need to be conceptually infinite. It is sufficient for it to exceed the limit of the space on the stack. This is also explained in the documentation:

StackOverflowException is thrown for execution stack overflow errors, typically in case of a very deep or unbounded recursion.

^{(emphasis mine)}

Answer 2

The cause of Stack overflow is in the 1st line:

  private void getNextTrack() {
    int currentTrack = new Random().Next(1, 30); // <- That's the cause

    if (playlist.Contains(currentTrack) ...)
      getNextTrack(); 

you re-create Random each time you call the method and since Random initializes from the system timer it returns the same value over and over again. Remedy: move Random from the method:

// Simplest, not thread-safe
private static Random generator = new Random(); 
...
private void getNextTrack()
{
   int currentTrack = generator.Next(1, 30);
   ...