-3

I have the following power function that I have written in c#:

public static double pow2(double x, double n)
{
    if (n == 0)
        return 1;
    else
    {
        stepAccumulator++;
        return pow2 (x, Math.Floor (n / 2.0)) * pow2 (x, Math.Ceiling (n / 2));
    }
}

When I run the program I simply say result=pow2(1,1000); and then time the function using a Stopwatch object and then print the result at the end. Unfortunately, when I run this program I get the following error: Process is terminated due to StackOverflowException. Why is this happening and how can I stop it?

Chizx
  • 351
  • 2
  • 5
  • 16
  • 5
    Yet again I have to ask: Does no one bother to debug code anymore? Surely you'd put a breakpoint at the top and check the value of `n` each time through? If you've done that why not tell us the results? If you haven't, why not do it? – John3136 Feb 19 '15 at 04:12
  • 5
    because n/2 is never 0 – Steve Mitcham Feb 19 '15 at 04:12
  • Nah, n reaches 0. On breakpoint, n=1000, n=500, n=250, n=125,.. n is divided by two each time and once it reaches 0, it never returns 1 with `if(n==0){return 1;}` and just continues to fluctuate between 0.0 and 1.0 – Chizx Feb 19 '15 at 04:15
  • 1
    Why would you think that repeatedly dividing a number by 2 will eventually give 0? That's not how math works. – Reticulated Spline Feb 19 '15 at 04:18
  • @ReticulatedSpline - note that code check is on `Ceiling`/`Floor` so `Floor(n/2)` eventually reaches 0 (unlike `Ceiling`)... Note that Floor/Ceiling let one to only compute whole powers... – Alexei Levenkov Feb 19 '15 at 04:23
  • Ah, I missed that. Apologies. – Reticulated Spline Feb 19 '15 at 04:25

1 Answers1

5

Your Math.Ceiling(n/2) case will never call pow with n == 0 because Math.Ceiling(1/2) == 1. Once your pow2 is called with n == 1 the next two calls will be:

return pow2 (x, Math.Floor (1 / 2.0)) * pow2 (x, Math.Ceiling (1 / 2));

Which is the same as :

return pow2 (x, 0) * pow2 (x, 1);

Which results in another call to pow2 with n == 1, so you algorithm never terminates

shf301
  • 31,086
  • 2
  • 52
  • 86
  • Thank you very much. That's the answer I was looking for. Unfortunately, there must be a way to solve this algorithm. It was given as an instruction to me to make a power function that works with that exact recursive call.. perhaps there is a way to rewrite this function into a working power function? The instruction was given to me by my professor who has a PhD in Algorithms. This must have a way to work, I must have written it incorrectly. – Chizx Feb 19 '15 at 04:23
  • You'll have to check on your instructions for that. Your algorithm doesn't look like a normal recursive implementation of power. Those usually only have one recursive call like the examples here: http://stackoverflow.com/questions/22389184/recursive-power-function-approach – shf301 Feb 19 '15 at 04:30