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

By | November 28, 2021

Problem

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

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

`8`

`23 = 8`

Approach

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

1. xy = x * xy-1
2. x0 = 1

The above properties resemble recursion as the second property is the base condition and according to the first property we can get xy by adding xy-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));
}```

`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;
}```

`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));
}
}```

`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))```

`8`