11.8. Homework 8 - A Recursive FunctionΒΆ

See also

Recursion

For this assignment, we will write our own function similar to the math library function pow(a, k), which computes a^k where a and k are both scalar values. For our function, we will restrict the scalar k to the set of positive integer numbers. The function prototype statement for our function might be:

double my_pow(double, unsigned int);

The basis for our recursive algorithm is the simple mathematical relationship

a^k = a^{{\left(k/2\right)}^2}.

By splitting k in half each time k is an even number, the number of multiplications is greatly reduced. Thus, our function should evaluate k to one of the following cases.

k == 0: a^0 = 1

k == 1: a^1 = a

k is an even number: a^k = a^{{\left(k/2\right)}^2}

k is an odd number: a^k = a\,a^{\left(k - 1\right)}