1

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.

Improve this question
1
  • 1
    The answer is obvious. Have you inspected the call stack in Visual Studio on exception? Just do that, and you'll be surprised. Commented Feb 26, 2015 at 14:13

2 Answers 2

Reset to default
4

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);
   ...
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Furthermore, if playlist should be populated with all values from 0 to 30, the if condition is met in every recursive call.
It's partialy true - after some amount of calls it will have new seed, though it probably won't matter anymore.
@PiRx what does seed mean?
@Chuker It's one of the most basic terms in the topic of pseudo-random number generation. You shouldn't have any problem in finding a lot of explanations on the internet :)
Found one here stackoverflow.com/questions/1785744/… Thank You so much :)
4

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)

Improve this answer

4 Comments

Add the fact, that new Random() is called on any call - it's probably initialized with same seed and generates same "bad" value. Keeping Random initialization out of recursive function would improve it. Second thing is that instead of recursion while loop would be much better choice for given algorithm. And there are more intelligent algorithms for achieving the same goal, but they probably are out of topic for current problem.
@PiRX Nice! Indeed, that's even more important here!
@PiRX you mean an Infinite while loop till I get the number?
@Chucker, in general - yes

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.