Simple calculate integer power of a double using recursion program - critique

I am trying to brush up on C after about 12+ years, which was two semesters at college. This program works, but I am poor on recursion and wonder if there are some tips that could be offered. Using Borland Turbo C++ 4.5 (yes, old) on win XP pro and win7 pro 32 bit machines.

Code:

/*  9.8 Mod listing 6.18 to all cases of integer powers using recursion */

#include <stdio.h>
double power(double a, int b);    /* function prototype  */

int main (void)
{
  double x, xpow;
  int n;

  printf("Enter a number and the integer power to which\n");
  printf("the number will be raised. Enter q to quit.\n");

  while(scanf("%lf%d", &x, &n) == 2)
  {
     xpow = power(x,n);
     printf("%.3e to the power %d is %.3e\n", x, n, xpow);
  }
  return 0;
}


double power(double a, int b)  /* POWER function  */
{
  double pow = 1;
  int b1;

  if (b == 0)            /* case of any number raised to 0 is 1 */
    return 1.0;

  else
  if (a == 0.0)          /* case of 0 to any power but 0 is 0  */
    return 0.0;

  else                   /* do non 0 pos and neg powers and numbers  */
  {
     if (b > 0)           /* normalize the power to a positive number  */
	b1 = b;            /* since fractions are not as accurate       */
     else
	b1 = -1 * b;

     pow = a;                 /*  calculate power doing recursive call  */
     pow *= power(pow, b1-1);

     if (b < 0.0)          /* case of negative exponents  */
	pow = 1.0/pow;

     return  pow;
  }
}

Your code is fine, but you can clean it up a bit by removing the temporary variables (b1 and pow), and eliminating some of the elses and nested if-elses. Also, you can combine some of your mathematical expressions:

Code:

double power2(double a, int b)
{
    if (b == 0) {
        // base case: anything to the 0 power is 1
        return 1.0;
    }


    if (a == 0.0) {
        // save us some time, 0 to any power other than 0 is 0
        return 0.0;
    }


    if (b < 0) {
        // b is negative, take the reciprocal of the positive version
        return 1 / (a * power2(a, -1 * b - 1));
    }

    // b is positive, normal recursion
    return a * power2(a, b - 1);
}

EDIT: You could also do the following, though I didn't mention it at first since I thought you didn't want to use any library functions:

Code:

return 1 / (a * power2(a, abs(b) - 1));

Thanks Andruil,
I used the elses to avoid doing the if checks if they were not required, a leftover from my assembly days when computers where slower and we watched the machine cycles.

I can see that your way is a bit neater, but I deliberately saved the negative power division until the last since (again, it could be just my age) the use of fractional math is less precise than the integer math (especially those that have non-finite decimal representations like 1/3) , so I waited until the last calculation to convert it. As far as the use of the absolute function, I did not want to drag in another library since the book has not gotten there yet, but you are correct, that is the better way in my example.

Ray

Pre-optimization is the root of all evil, so they say. On a desktop machine, never count cycles unless you know that it's a serious bottleneck and the speed up will be significant. Otherwise, such optimization can easily become a maintenance nightmare. I started in real-time embedded systems over a decade ago, so I had to fight the same urge to optimize at an assembly code level when I got my second job programming enterprise level business software where resources abounded.

Your code and my code will always have to make the same 3 comparisons in order, regardless of the use of "else". We both check a base case. If that's false, we check if a is zero (to short-circuit the recursion). If that's false too, we then check if b is positive or negative, so we can compute the right kind of exponent. Use of else if might provide a more optimized solution (e.g. jump table) if you compared b against several discreet values, like

Code:

if (b == 0)
else if (b == 1)
else if (b == 2)
else if (b == 3)
else if (b == 4)
else if (b == 5)
else

This is similar to a switch statement. But this doesn't work for us since we have to check b, then a, then b again.

My version is probably a little quicker since I don't do any extra comparisons (you check b for positive/negative in two places), and I don't use (and thus don't have assignments to) temporary variables. Granted these are probably pretty negligible time-savers, but if you really care...

As for waiting until the last minute to take the reciprocal, my code does that as well, due to the parentheses around the (a * power2(a, -1 * b - 1)), which is not only mandatory for a correct answer, but it forces that to be calculated before the division. That code will only ever be executed on the first run through this function. All recursive calls after that will have a non-negative b value and thus can't execute another division. It will be the last operation before a value is returned to your main function. If you don't want to use abs(), you may do a few cycles better by using 0 - b - 1 instead of -1 * b - 1, though the compiler may optimize the multiplication out anyhow.

Thanks Anduril, I did not read your code correctly. Told you I was poor on recursion. Have to study what you did a bit more since I have a feeling I will have that type of flow show up again. And now that you mention it, I remember an instructor telling us back in the early 80's that the new compilers will/should be doing that optimization, so another thing to watch for so as to not over complicate the picture.

Thanks for taking the time to do that analysis.

Ray

Originally Posted by anduril462

Granted these are probably pretty negligible time-savers, but if you really care...

... you would use a faster algorithm
For example:

Code:

double power(double a, int b)
{
    if (b == 0)
    {
        /* base case: anything to the 0 power is 1 */
        return 1.0;
    }
    else if (a == 0.0)
    {
        /* save us some time, 0 to any power other than 0 is 0 */
        return 0.0;
    }
    else if (b < 0)
    {
        /* b is negative, take the reciprocal of the positive version */
        return 1.0 / power(a, -b);
    }
    else
    {
        /* b is positive, normal recursion */
        double result = power(a, b / 2);
        result *= result;
        if (b % 2 != 0)
        {
            /* account for the truncation of b / 2 due to integer division */
            result *= a;
        }
        return result;
    }
}

Originally Posted by laserlight

... you would use a faster algorithm
For example:

Code:

        return result;
    }
    /* <------ */
}

Not having a return before the final brace on a function that returns something other than void, bugs the crap out of me.


Quzah.

Originally Posted by quzah

Not having a return before the final brace on a function that returns something other than void, bugs the crap out of me.

Go ahead and insert unreachable code if that makes you feel better

Or you can change the function to have a single exit point, but then anduril462 will tell you that "you can clean it up a bit by removing the temporary variable".

Oh, but I guess the best solution for you is to remove the else so control just carries on, but you'll have to declare result far from where it will be first used according to your preferred style.

Originally Posted by laserlight

Go ahead and insert unreachable code if that makes you feel better

Or you can change the function to have a single exit point, but then anduril462 will tell you that "you can clean it up a bit by removing the temporary variable".

Oh, but I guess the best solution for you is to remove the else so control just carries on

Yeah, I would have probably ditched the else. Trying to make it use no variables and a single return is ugly.

I know it's not going to reach that point, but I can't bring myself to do that.


Quzah.

Originally Posted by laserlight

Go ahead and insert unreachable code if that makes you feel better

LOL!
Love that comment eh - so true!