Multiplying to powers using recursion

I am looking for a way to code a program which will multiply an integer to an exponent using only a recursion loop. I have a very limited understanding of recursion, but have been able to code something to give a factorial:

int fac2(int n)
{
    if (n == 1){
        return 1;
    } else {
        return n*fac2(n-1);
    }
}

I have a way to find a power already, but it use开发者_运维问答s a for loop:

int my_power(int x, int e)
{
    int i, total;
    total = 1;
    for (i = 1; i <= e; i++){
    total *= x;
    }
    return total;
}

How can I replace this for loop using recursion?

int my_power (int x, int e) {
  if (e == 0) return 1;

  return x * my_power(x, e-1);
}

Remember that a recursive function calls itself until some base case is achieved. What is your base case here? Raising a number to a power is liking saying that you are going to multiply some number x amount of times. The hint is to call the recursive function, reducing the power by one until you reach your desired base case.

Use Dave Anderson's as a basis, but also consider the special cases of where:

1) x is 0 
2) e is negative.

Again, no code so you can try to figure it out yourself :-)

Update: Make sure you create a number of test cases, and you make sure everyone works as you think it should. Once the tests pass, you'll know that your recursive power function is working correctly.

Example: Having had time to figure it out yourself, I though I'd present a solution, with tests:

int main(void)
{
    // n = 0 special case
    test(0, 0, 1);
    test(4, 0, 1);
    test(-5, 0, 1);

    // x = 0 special case
    test(0, 0, 1);
    test(0, 2, 0);

    // normal use
    test(4, 1, 4);
    test(4, -1, 0.25);
    test(-4, 3, -64);
    test(8, 2, 64);
    test(2, 3, 8);
    test(2, -3, 0.125);
    test(2, -5, 0.03125);

    // Invalid input tests
    std::cout << std::endl << "Invalid input tests" << std::endl;
    test (0, -2, NULL);
    test(0, -4, NULL);


    // Negative Tests
    std::cout << std::endl << "Negative tests (expect failure)" << std::endl;
    test(4, 0, 4);
    test(2, 1, 1);
    test(2, -5, 0.0313);

    return 0;
}

double power(int x, int n)
{
    // check for invalid input
    if (n == 0)
    {
        return 1;
    }

    if (n > 0)
    {
        return x * power(x, n - 1);
    }
    else if (n < 0)
    {
        return 1 / (x * power(x, -n - 1));
    }
}

bool test(int x, int n, double expected)
{
    if (x == 0 && n < 0)
    {
        std::cout << "Testing " << x << "^" << n << ", result = 'Invalid input'." <<  std::endl;
        return false;
    }

    double result = power(x, n);
    std::cout << "Testing " << x << "^" << n << ", result = " << result << ". Expected " << expected << " - test " << ((result == expected) ? "PASSED" : "FAILED") <<  std::endl;
    return true;
}

Output:

Testing 0^0, result = 1. Expected 1 - test PASSED
Testing 4^0, result = 1. Expected 1 - test PASSED
Testing -5^0, result = 1. Expected 1 - test PASSED
Testing 0^0, result = 1. Expected 1 - test PASSED
Testing 0^2, result = 0. Expected 0 - test PASSED
Testing 4^1, result = 4. Expected 4 - test PASSED
Testing 4^-1, result = 0.25. Expected 0.25 - test PASSED
Testing -4^3, result = -64. Expected -64 - test PASSED
Testing 8^2, result = 64. Expected 64 - test PASSED
Testing 2^3, result = 8. Expected 8 - test PASSED
Testing 2^-3, result = 0.125. Expected 0.125 - test PASSED
Testing 2^-5, result = 0.03125. Expected 0.03125 - test PASSED

Invalid input tests
Testing 0^-2, result = 'Invalid input'.
Testing 0^-4, result = 'Invalid input'.

Negative tests (expect failure)
Testing 4^0, result = 1. Expected 4 - test FAILED
Testing 2^1, result = 2. Expected 1 - test FAILED
Testing 2^-5, result = 0.03125. Expected 0.0313 - test FAILED

The right way of doing what you want is by noticing that:

• xⁿ = (x^n/2)², if n is even
• xⁿ = x * (x^⊦n/2⫞)², if n is odd
• x¹ = x
• x⁰ = 1

where "⊦n/2⫞" means the integer part of n/2 (which is what n/2 gives you in C when n is an integer variable).

Contrasting with the factorial, which reads

• n! = n * (n - 1)!, if n > 0
• 0! = 1

you should be able to write a recursive program for exponentiation basing yourself on the factorial.

There's a way of thinking about this that requires us stepping outside of C-land, but it's so simple at it's heart and powerful it's well worth considering.

Recursion and iteration aren't so different as they first seem. At a certain level, it's actually hard to tell them apart. We won't quite go there, but consider this recursive implementation of a for "loop" (in no particular language):

for (i, n, f, a) = 
  if (i > n) {
    return a
  } else {
    return for (i+1, n, f, f(a, i))
  }

(The a, by the way, is called an "accumulator", because it accumulates the value of each "loop")

The one thing that might be new to you is that the above treats functions like any other data type, which is something called "first-class functions". This isn't typically something you do in C (you can do it in a limited fashion by passing function pointers), but it's so powerful a concept that it's well worth learning.

Using the above definition of for, we write your factorial function as:

mult(a,b) = a*b
fac(n) = for (1, n, mult, 1)

This putts along, multiplying each i by the accumulator.

Another powerful concept (that, sadly, C doesn't support at all) is anonymous functions, which are simply functions created without names. I'm going to use the syntax e -> ... for anonymous functions, where ... is some expression (e.g. x -> x+1), and (a,b) for a pair of variables. In C, anonymous functions might seem useless, but if you can pass around functions as easily as you can pass around numbers, you can simplify fac to a single line:

fac(n) = for (1, n, (a,i) -> a*i, 1)

pow can be written as:

pow(x, e) = for(1, e, (a,i) -> a*x, 1) 

Expand for in that, and you've got a recursive definition for pow.

Though this gives you a recursive function, there is another implementation (Alexandre's, in fact) that's more time efficient.

This function will, to the best of my knowledge, for any likely case (someone setting "asdfj" as x or e is not likely) work.

#include <stdio.h>

double my_power(int x, int e)
{
    if (x == 0)
    {
        return 0;
    }
    if (e == 0)
    {
        return 1;
    }
    if (e > 0)
    {
        return x * my_power(x, e-1);
    }
    if (e < 0)
    {
        return 1/(x*my_power(x, -e-1));
    }
}

Here's a pseudo-code for you:

FUNCTION mypower(number, exponent)
    IF exponent == 0 THEN:
        RETURN 1
    ELSE IF exponent > 0 THEN:
        RETURN number * mypower(number, exponent - 1)
    ELSE:
        RETURN 1 / mypower(number, -(exponent))

And oh, the return value should be double.

Here's the actual code:

double mypower(int n, int e) {
    if (e == 0)
        return 1;
    else if (e > 0)
        return n * mypower(n, e - 1);
    else
        return 1 / mypower(n, -e);
}