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\n", 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

Here is a solution in ruby which works for negative exponents as well

# for calculating power we just need to do base * base^(exponent-1) for ex:
# 3^4 = 3 * 3^3
# 3^3 = 3 * 3^2
# 3^2 = 3 * 3^1
# 3^1 = 3 * 3^0
# 3^0 = 1

# ---------------------------------------------------------------------------
# OPTIMIZATION WHEN EXPONENT IS EVEN
# 3^4 = 3^2 * 3^2
# 3^2 = 3^1 * 3^1
# 3^1 = 3^0
# 3^0 = 1
# ---------------------------------------------------------------------------

def power(base, exponent)
  if(exponent.zero?)
    return 1
  end
  if(exponent % 2 == 0)
    result = power(base, exponent/2)
    result = result * result
  else
    result = base * power(base, exponent.abs-1)
  end

  # for handling negative exponent
  if exponent < 0
    1.0/result
  else
    result
  end
end

# test cases
puts power(3, 4)
puts power(2, 3)
puts power(0, 0)
puts power(-2, 3)
puts power(2, -3)
puts power(2, -1)
puts power(2, 0)
puts power(0, 2)

Answer 2

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