(academic) math recursion question

[mark]

consider:
Int64 steps = 0;
public Int64 recurse(double A)
{
steps += 1;
A = A/2;
try
{
A = recurse(A);
}
catch
{
return steps;
}
return 1; //To satisfy return on all code paths (never reached).
}

At the point of underflow I would expect a stack overflow exception to
trigger the directive in the catch block. But it does not. Rather, it halts
execution in the try block with: "An unhandled exception of type
'System.StackOverflowException' occurred".

Stipulating that a recursive procedure be used, and stipulating that testing
to the known underflow threshold not be performed, how can this
implementation be made functional?

 

[Hans Kesting]

mark submitted this idea :

consider:
Int64 steps = 0;
public Int64 recurse(double A)
{
steps += 1;
A = A/2;
try
{
A = recurse(A);
}
catch
{
return steps;
}
return 1; //To satisfy return on all code paths (never reached).
}

At the point of underflow I would expect a stack overflow exception to
trigger the directive in the catch block. But it does not. Rather, it halts
execution in the try block with: "An unhandled exception of type
'System.StackOverflowException' occurred".

Stipulating that a recursive procedure be used, and stipulating that testing
to the known underflow threshold not be performed, how can this
implementation be made functional?

From MSDN:

In prior versions of the .NET Framework, your application could catch a
StackOverflowException object (for example, to recover from unbounded
recursion). However, that practice is currently discouraged because
significant additional code is required to reliably catch a stack
overflow exception and continue program execution.

Starting with the .NET Framework version 2.0, a StackOverflowException
object cannot be caught by a try-catch block and the corresponding
process is terminated by default. Consequently, users are advised to
write their code to detect and prevent a stack overflow. For example,
if your application depends on recursion, use a counter or a state
condition to terminate the recursive loop. Note that an application
that hosts the common language runtime (CLR) can specify that the CLR
unload the application domain where the stack overflow exception occurs
and let the corresponding process continue. For more information, see
ICLRPolicyManager Interface and Hosting the Common Language Runtime.

http://msdn.microsoft.com/en-us/library/system.stackoverflowexception.aspx

Hans Kesting

 

[Marc Gravell]

http://msdn.microsoft.com/en-us/library/system.stackoverflowexception.aspx

"Starting with the .NET Framework version 2.0, a
StackOverflowException object cannot be caught by a try-catch block
and the corresponding process is terminated by default."
"A thrown StackOverflowException cannot be caught by a try-catch
block. Consequently, the exception causes the process to terminate
immediately. "

Now, truth be told I've never looked very hard [if I blow the stack, I
assume I've done something very, very wrong] - but AFAIK there is no
obvious way to do it... again: I've not looked very hard!

Marc

 

[Ben Voigt [C++ MVP]]

consider:
Int64 steps = 0;
public Int64 recurse(double A)
{
steps += 1;
A = A/2;
try
{
A = recurse(A);
}
catch
{
return steps;
}
return 1; //To satisfy return on all code paths (never
reached). }

At the point of underflow I would expect a stack overflow exception to
trigger the directive in the catch block. But it does not. Rather, it

If you want you detect underflow, best put "A = A/2;" in a checked block.
Or test if ((A/2)*2 == A).

But in any case I don't think you understand exception handling, based on
your comment on the return statement. Assuming that a catchable exception
is thrown, the next outer stack frame will catch it and execute "return
steps;" thereby returning normally. Thus the next outer frame will finish
the try block without exception, and hit the "never reached" return 1
statement, also returning normally. It is trivial to show by induction (you
did say math question) that any deeper number of calls will also ultimately
return 1. The key point is that the exception is caught by the innermost
enclosing (matching) exception handler, is does not jump to the outermost
frame of the recursion.

Perhaps you meant the catch block to say "return recurse(A);"? In that case
the "return 1;" outside the block would indeed be unreachable and could be
removed.

 

[mark]

OK, Something like this works:

Int64 steps = 0;
public Int64 recurse(double A)
{
steps += 1;
if ((A / 2) * 2 != A)
{
return steps-1;
}
A = A/2;
return recurse(A);
}

It's interesting that the A/2 in the conditional does not throw the overflow
error.

 

[Ben Voigt [C++ MVP]]

OK, Something like this works:

Int64 steps = 0;
public Int64 recurse(double A)
{
steps += 1;
if ((A / 2) * 2 != A)
{
return steps-1;
}
A = A/2;
return recurse(A);
}

It's interesting that the A/2 in the conditional does not throw the
overflow error.

Why would it? It can only underflow, not overflow.

You do realize that the StackOverflowException was due to infinite recursion
and not due to floating point underflow?

Here is an improvement though:

Int64 steps = 0;
public Int64 recurse(double A)
{
double A2 = A / 2;
if (A2 * 2 != A)
{
return steps;
}
steps++;
return recurse(A2);
}

Or, going purely functional:

public Int64 recurse(double A)
{
double A2 = A / 2;
if (A2 * 2 != A)
{
return 0;
}
return recurse(A2) + 1;
}

 

[mark]

You do realize that the StackOverflowException was due to infinite recursion
and not due to floating point underflow?

My problem was that I did not understand this.

Thanks

 

[Hans Kesting]

mark presented the following explanation :

OK, Something like this works:

Int64 steps = 0;
public Int64 recurse(double A)
{
steps += 1;
if ((A / 2) * 2 != A)
{
return steps-1;
}
A = A/2;
return recurse(A);
}

It's interesting that the A/2 in the conditional does not throw the overflow
error.

When I try this (in SnippetCompiler) I still get a stack overflow. I
added some Writeline statements to find out it reached about 40.000
steps. The value of A was 0 from step 1075 (I started with 1.0).

The test "(A / 2) * 2 != A" is the problem here: it is true for A==0,
but the bigger problem is: will it work correctly for a non-zero value?

Hans Kesting

 

[mark]

Hans,

With VS2005 C# code, the recursion is stable for values of A except A==0
(for which A/0 does not change and is never equal to A).