[C#] Fatal stack overflow

[Jesper Stocholm]

I have a recursive function that I would like to do a lot of recursive
calls (preferebly 2^20 in total)

The function is called as (with maxi = e.g. 100000)

DoRecursion(0,maxi,bseed,sha);

And the total code is

static void Main(string[] args)
{
long maxi = Convert.ToInt64(args[0]);
try
{
SHA1 sha = new SHA1CryptoServiceProvider();
// initial seed
string seed = System.Guid.NewGuid().ToString();
byte[] bseed = (new UTF8Encoding()).GetBytes(seed);

System.DateTime time1 = DateTime.Now;
DoRecursion(0,maxi,bseed,sha);
System.DateTime time2 = DateTime.Now;

// interval is created
System.TimeSpan interval = time2 - time1;
Console.WriteLine("Milliseconds: \t {0}",interval.TotalMilliseconds.ToString());
}
catch (Exception e)
{
Console.WriteLine("Error: {0}",e.Message);
}
}

private static void DoRecursion(long i, long maxi, byte[] seed, SHA1 sha1)
{
try
{
byte[] result;
result = sha1.ComputeHash(seed);
if (i < maxi)
{
i++;
DoRecursion(i,maxi,result,sha1);
}
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}
}

But every time I reach a value 15196 for i, I get the error "Fatal stack
overflow error."

What am I doing wrong?

 

[Bret Mulvey [MS]]

Nesting function calls a million levels deep is hardly ever a good idea, and
I don't see anything in this function that would require recursion. It looks
like you're applying SHA1 to an array of bytes over and over again and not
doing anything with the result except for timing it. You should be able to
replace your recursive function with a simple loop.

If you really do need to use recursion for some reason that's not
illustrated here, you can cut down on the number of parameters you put on
the stack for each call. Based on what the function actually does, you could
make them all member variables and not pass any of them on the stack.

 

[Michael Giagnocavo [MVP]]

A case for C# tailcalls?

The managed stack is only 1MB by default (AFAIK). So, if you do enough
recursion to allocate more than that, you'll get this exception. I'd
suggest moving the recursion to inside one method.

-mike
MVP

 

[Richard A. Lowe]

If you can't re-write the method as Bret suggested, you can take the easy
way out and just significantly up the stock size (if you have the editbin
tool available):
http://blogs.geekdojo.net/richard/posts/207.aspx

 

[Jesper Stocholm]

Bret Mulvey [MS] wrote :

Nesting function calls a million levels deep is hardly ever a good
idea, and I don't see anything in this function that would require
recursion. It looks like you're applying SHA1 to an array of bytes
over and over again and not doing anything with the result except for
timing it. You should be able to replace your recursive function with
a simple loop.

Yes - what I am doing is creating a chain of hash-values, so the output
of SHA1 is in the next recursion used as input to SHA1.

If you really do need to use recursion for some reason that's not
illustrated here, you can cut down on the number of parameters you put
on the stack for each call. Based on what the function actually does,
you could make them all member variables and not pass any of them on
the stack.

I re-wrote the recursive method to a FOR-loop instead that updates a
member variable. It now works like a charm.

Thanks,