K

#### Keith Thompson

BartC said:A simple example which is related (in being numeric) but better (as it is

genuinely useful) is the following code to calculate the integer power of a

integer:

#include <stdint.h>

uint64_t upower(uint64_t a, int n) {

if (n<=0)

return 0; /* use 0 for fractional results */

else if (n==0)

return 1;

else if (n==1)

return a;

else if ((n & 1)==0)

return upower(a*a, n/2);

else

return upower(a*a, (n-1)/2)*a;

}

An iterative version (which doesn't just do n-1 multiplications) is not

impossible, but the recursive method is more natural.

Some quibbles (none of which are meant to detract from the main point):

Surely upower(1, -1) should be 1, not 0. upower(0, -1) (or with any

negative exponent) is an error; it's not clear how that should be

handled. You might make n an unsigned int, since negative exponents

aren't particularly useful for an integer power function.

In the last return statement, (n-1)/2 could be written as n/2, since n

is odd and integer division truncates anyway. I might put the

multiplication by a at the beginning of the expression, just to make it

stand out more:

return a * upower(a*a, n/2);