I had to make a recursive function that use only multiplication operation to get the answer of X in power of N.

I wrote this:

#include <stdio.h>

int power(int x, int n);

int main()
{
    int x, n;
    printf("Enter base and exponent:\n");
    scanf("%d%d", &x, &n);
    printf("%d\n", power(x, n));
    return 0;
}

int power(int x, int n)
{
    if (n==0) return 1;
    return x*power(x, n*0.5);
}

So its works good for small number, like if the input x=3, n=2 the output will be 9 which is good. But when I input bigger numbers, for example: x=362, n=123 the output will be -79249792 which its wrong.

Can someone help me understand what's wrong?

(Im using Online C Compliler {OnlineGBD})

CodePudding user response：

First, the recursion you implemented shouldn't work for small numbers too, since as others have pointed out, x^n = (x^(n/2))^2 and not x*(x^(n/2)), and for odd values of n, n/2 will get truncated since the function takes integer arguments. Try 2^3, your code gives answer 4. A simple way to fix this is via using the following recursion : x^n = x*(x^(n-1)), or if you want to make the code more efficient, use this algorithm.

But this still doesn't address negative numbers showing up. The problem is max size of int is 2^31-1 = 2,14,74,83,647. This is due the way it is stored in memory, occupying 32 bits. What happens when you cross this limit? It overflows, and becomes -2^31. So you won't be able to get correct answers for big numbers. Generally this is handled by calculating the answer modulo some prime number, or creating arbitrary precision data structures. Check out this and this.

CodePudding user response：

First of all, please remove this:

printf("Enter base and exponent:\n");
scanf("%d%d", &x, &n);
printf("%d\n", power(x, n));

and write a simple, easy to run test harness that doesn't involve thinking and typing input into the console, with clear output of expected/actual values on failure:

#include <math.h>
#include <stdio.h>

int power(int base, int exponent) {
    return 1;
}

int main(void) {
    for (int base = 0; base < 5; base  ) {
        for (int exponent = 0; exponent < 5; exponent  ) {
            int expected = (int)pow(base, exponent);
            int actual = power(base, exponent);

            if (expected != actual) {
                printf("[FAIL] power(%d, %d) was: %d\n"
                       "              expected: %d\n\n",
                       base, exponent, actual, expected);
            }
        }
    }

    return 0;
}

Notice the clearer parameter names on the power function and usage of the built-in pow to ensure correct logic.

Now let's test your algorithm:

[FAIL] power(2, 3) was: 4
              expected: 8

[FAIL] power(2, 4) was: 8
              expected: 16

[FAIL] power(3, 3) was: 9
              expected: 27

[FAIL] power(3, 4) was: 27
              expected: 81

[FAIL] power(4, 3) was: 16
              expected: 64

[FAIL] power(4, 4) was: 64
              expected: 256

It appears that n*0.5 isn't giving the correct reduction factor.

Taking a step back, exponentiation by multiplication is done by repeatedly multiplying base by itself exponent times and accumulating onto a result initialized to 1:

int power(int base, int exponent) {
    int result = 1;

    for (int i = 0; i < exponent; i  ) {
        result *= base;
    }

    return result;
}

Since we're forced to use recursion, the problem reduces to simulating the classic counting loop above with recursion.

This can be done by subtracting 1 from the exponent per call until we reach 0 (<= 0 is a safer base case than == 0, avoiding blowing the stack on negative input).

As for the return value, you're correct in returning 1 for n == 0 and multiplying base on each frame by the child's value, which is the same as the *= operation in the iterative version.

Here's the fixed code:

int power(int base, int exponent) {
    if (exponent <= 0) {
        return 1;
    }

    return base * power(base, exponent - 1);
}

Finally, x=362, n=123 fails because of integer overflow. 362**123 has 315 digits, but 4 byte numbers like int only hold 10-ish. You'll need a big integer library to handle that massive an input.

Note that I haven't attempted to handle negative numbers here. I assume that's out of scope. Making the parameters unsigned would help enforce this contract.