CODEWITHSUNDEEP
c#randomstackoverflow
AgarOther
AgarOther

Reputation: 1

C# : Stack Overflow Exception during recursive method

I have a recursive method that calls itself whenever the random generated number isn't equal to 1. I'm trying to test odds on different things such as a shiny pokemon (1/8192) or a 12-eyes seed in Minecraft (10^12), even though I understand why the Stack Overflow is happening, I don't know how to fix it. Using Threads slows it down by a lot (5000 calculations/s without, around 500 with threading).

Here's the code:

static void shiny()
{
    total = 0;
    counter += 1;
    resetcounter += 1;
    if (rdm.Next(8192) + 1 == 1)
    {
        Console.WriteLine("SHINY !! In: " + counter + " resets.");
    }
    else
    {
        if (resetcounter > 7000)
        {
            Console.WriteLine("Reset. Current: " + counter);
            ThreadStart newtask = new ThreadStart(shiny);
            Thread task = new Thread(newtask);
            task.Start();
        }
        else
        {
            Console.WriteLine("Reset. Current: " + counter);
            shiny();
        }
    }
}

I use the resetcounter variable to avoid the Stack Overflow error since it's happening around 7k "resets", then it starts a new thread. I'd love to understand how testing odds can avoid stack overflow though !

Upvotes: 0

Views: 129

Answers (1)

JonasH
JonasH

Reputation: 36341

for some background info. C# and many other languages uses a call stack when calling methods, this is used for local variables, return values and other stuff. The size of the stack will therefore increase when you call a method, and decreases the same amount when the method returns. The max size is usually 1-4Mb and is quite easy to reach when using recursive code without a well defined max depth.

Recursive functions can be re-written as iterative functions. Some cases need an explicit stack that can be much larger, but that is not needed in this case. The example code, minus the threading, could be rewritten as follows:

    void shiny()
    {
        while (rdm.Next(8192) != 0)
        {
            counter += 1;
        }
        Console.WriteLine("SHINY !! In: " + counter + " resets.");
    }

While experiments like this can be fun, you can calculate probabilities explicitly. Assuming the chance of finding a shiny in one round is one in 8192, or 0.012%, the chance of finding at least one shiny after n rounds would be 1 - (8191/8192)^n. Throw that into wolfram alpha and you get a probability plot.

Upvotes: 2

Related Questions