c - Recursive power function: approach

Question

I'm programming for a while now(beginner), and recursive functions are a somewhat abstract concept for me. I would not say I'm stuck, program works fine, I'm just wondering if the function itself could be written without the pow function in the code (but still doing exactly what the problem suggests)

Problem: http://prntscr.com/30hxg9

My solution:

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

int power(int, int);

int main(void)
{
    int x, n;
    printf("Enter a number and power you wish to raise it to: ");
    scanf_s("%d %d", &x, &n);
    printf("Result: %d
", power(n, x));
    return 0;
}

int power(int x, int n)
{
    if (n == 0) return 1;
    if (n % 2 == 0) return pow(power(x, n / 2), 2);
    else return x * power(x, n - 1);
}

I've tried doing this: power(power(x, n - 1), 2); but execution failed, and I'm still backtracking why.

Answer 1

When rewriting your function, don't lose sight of the main benefit of recursion in this case, which is to reduce the number of multiplication operations required. For example, if n = 8, then it is much more efficient to compute x * x as val1, then val1 * val1 as val2, and the final answer as val2 * val2 (3 multiplications) than to compute x * x * x * x * x * x * x * x (7 multiplications).

This difference is trivial for small integers but matters if you put this operation inside a big loop, or if you replace the integers with very large number representations or maybe ginormous matrices.

Here's one way to get rid of the pow() function without getting rid of the recursion efficiency:

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

int power(int, int);

int main(void)
{
    int x, n;
    printf("Enter a number and power you wish to raise it to: ");
    scanf_s("%d %d", &x, &n);
    printf("Result: %d
", power(x, n));
    return 0;
}

int power(int x, int n)
{
    int m;
    if (n == 0) return 1;
    if (n % 2 == 0) {
        m = power(x, n / 2);
        return m * m;
    } else return x * power(x, n - 1);
}