# Implement power function without using multiplication & division operators (Recursive Approach)

Posted in  Vinay Khatri
Last updated on December 7, 2023

## Problem

Given two positive integers x and y, implement x y without using multiplication or division operator

#### Sample Input

```x = 2
y = 3```

`8`

#### Explanation

`23 = 8`

## Approach

We will use the below properties of exponents to solve this problem:

1. x y = x * x y-1
2. x 0 = 1

The above properties resemble recursion as the second property is the base condition and according to the first property we can get x y by adding x y-1 upto x times.

### Complexity Analysis

The time complexity is O(max(x, y)) with space complexity O(y) due to the call stack.

#### C Programming

``````#include <stdio.h>
// implement power function
int solve(int x, int y)
{
// base case
if (y == 0) {
return 1;
}

int ans = 0;

//recursive call
int exp = solve(x, y - 1);

for (int i = 0; i < x; i++) {
ans += exp;
}
return ans;
}

void main()
{
printf("%d", solve(2, 3));
}``````

#### Output

``8``

#### C++ Programming

``````#include <iostream>
using namespace std;

// implement power function
int solve(int x, int y)
{
// base case
if (y == 0) {
return 1;
}

int ans = 0;
int exp = solve(x, y - 1);   //recursive call

for (int i = 0; i < x; i++) {
ans += exp;
}
return ans;
}

int main()
{
cout << solve(2, 3);
return 0;
}``````

#### Output

``8``

#### Java Programming

``````class Main
{
// implement power function
public static int solve(int x, int y)
{
// base case
if (y == 0) {
return 1;
}

int ans = 0;
int exp = solve(x, y - 1);   // recursive call

for (int i = 0; i < x; i++) {
ans += exp;
}

return ans;
}

public static void main(String[] args) {
System.out.print(solve(2, 3));
}
}``````

#### Output

``8``

#### Python Programming

``````# implement power function
def solve(x, y):
# base case
if y == 0:
return 1

exp = solve(x, y - 1)  #recursive call

ans = 0
for i in range(x):
ans += exp

return ans

print(solve(2, 3))``````

#### Output

``8``