Program to calculate power using recursion

Introduction

In this, we are given two numbers, x, and y. Here we need to find x^y using recursion.

Problem Statement

We are given two numbers, x, and y, by the user, and we have to calculate x^y using recursion. We have to write a function that calculates the value of x^y, taking two numbers x and y as input and printing the output.

Input: 
2 2

Output: 
4

Explanation: 2^2 = 4

Input 2:
3 3

Output 2: 
9

Explanation:- 3^3 = 9

Approach

The approach is quite simple here. We have to write a function that will take two parameters, x and y. And it will print the output using Recursion. The approach will be clearer as we head towards code—algorithm

1. Declare three variables x, y, res.
2. Take input of x and y.
3. Call the CalPower function with two parameters, x, and y.
4. Assign that function to res variable as it will return the value after calculation.
5. The if block will keep on calling the same function by decreasing the value of y by one each time.
6. When the value of y becomes zero, it will return one as the power to any number is 0.
   Ex:- 2^0 = 1 or 1000^0=1.(base case)
7. And finally, it will return the calculated value to the function call in the main block.

Implementation in C++

C++ program for the above approach is given below:

import java.util.*;
public class Main {
  public static int CalPower(int x, int y) {
    if (y != 0)
      return (x * CalPower(x, y - 1)); =
    // base case
    else
      return 1;
  }
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int x, y, res;
    System.out.println("Enter base number: ");
    x = sc.nextInt();
    System.out.println("Enter power number(positive integer): ");
    y = sc.nextInt();
    res = CalPower(x, y);
    System.out.println(x + " ^ " + y + " = " + res);
  }
}

You can also try this code with Online C++ Compiler

Run Code

Input:

2 2

Output:

Enter base number:
Enter power number(positive integer):
2^2 = 4

Implementation in Java

Java Program for the above approach is given here:

import java.util.*;
public class Main {
  public static int CalPower(int x, int y) {
    if (y != 0)
      return (x * CalPower(x, y - 1)); =
    // base case
    else
      return 1;
  }
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int x, y, res;
    System.out.println("Enter base number: ");
    x = sc.nextInt();
    System.out.println("Enter power number(positive integer): ");
    y = sc.nextInt();
    res = CalPower(x, y);
    System.out.println(x + " ^ " + y + " = " + res);
  }
}

You can also try this code with Online Java Compiler

Run Code

Input:

2 2

Output:

Enter base number:
Enter power number(positive integer):
2^2 = 4

Try and compile with online c++ compiler.

Complexity Analysis

Time Complexity: O(n)

Explanation: 

Let  t(n) the time wanted through CalPower(x,n), i.e., a feature of n, Then we will conclude that t(0)=c, due to the base case pow(x,0), we've got to test whether (n==0), which return 1.

• On expanding the term t(n):
  

Image source

After expanding we have seen that every time the value of n decreases one d is added because d is a constant here or an operation that takes constant time. At the end when n==0, we would have n d’s, which means n*d +c. As we know d, c is constant, so we can ignore them and can say that the time complexity is O(n).

Space Complexity: O(n)
As we have seen above the relation, let us understand it better by an example, If x=2 and y=4, then CalPower(2,4) will be called. So this call will be stored on the stack in a heap. Now the function will be called again by decreasing y by1. CalPower(2,3) will be stored on the stack. Now, there are two calls.

For CalPower(2,3), CalPower(2,2) will be called. Now there are three calls on the stack.
For CalPower(2,2), CalPower(2,1) will be called. Now there will be four calls on the stack.
Finally, for CalPower(2,1), CalPower(2,0) will be called the base case and will return 1.

So approximately, the stack had four calls on the stack, which was equal to the power we had entered.

So the complexity would be O(y) or O(n), as we generally say.

Also check out - Rod Cutting Problem