By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,712 Members | 1,430 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,712 IT Pros & Developers. It's quick & easy.

[C#] Fatal stack overflow

P: n/a
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?

--
Jesper Stocholm
http://stocholm.dk
Give a man a fish and he will have food for a day,
give a man an elephant, and he will have food for a week.
Nov 15 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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.

"Jesper Stocholm" <j@stocholm.invalid> wrote in message
news:Xn***********************@192.38.208.86...
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?

--
Jesper Stocholm
http://stocholm.dk
Give a man a fish and he will have food for a day,
give a man an elephant, and he will have food for a week.

Nov 15 '05 #2

P: n/a
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

"Jesper Stocholm" <j@stocholm.invalid> wrote in message
news:Xn***********************@192.38.208.86...
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?

--
Jesper Stocholm
http://stocholm.dk
Give a man a fish and he will have food for a day,
give a man an elephant, and he will have food for a week.

Nov 15 '05 #3

P: n/a
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

--
Veuillez m'excuser, mon Français est très pauvre. Cependant, si vous voyez
mauvais C #, c'est mon défaut!
"Jesper Stocholm" <j@stocholm.invalid> wrote in message
news:Xn***********************@192.38.208.86...
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?

--
Jesper Stocholm
http://stocholm.dk
Give a man a fish and he will have food for a day,
give a man an elephant, and he will have food for a week.

Nov 15 '05 #4

P: n/a
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, :)

--
Jesper Stocholm
http://stocholm.dk
Give a man a fish and he will have food for a day,
give a man an elephant, and he will have food for a week.
Nov 15 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.