(academic) math recursion question

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?

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.

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?

mark wrote:>
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.
>>
>
>

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.

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.
>

mark presented the following explanation :>
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
>
>
>