Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Optimized Approach
4.1.
Optimized Algorithm
4.2.
Optimized Implementation
4.2.1.
Time Complexity
4.2.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is Recursion?
5.2.
Does recursion follow any rules?
5.3.
What is the recursive method?
5.4.
Name the different types of recursion.
5.5.
What is the recursion tree method?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Finding Power Recursively in Carbon

Author Ayush Mishra
1 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Hey Ninjas! Do you know the new programming language developed by Google? Carbon is a programming language recently developed by Google on 19th July 2022, and it is implemented using C++ language.

In this blog, we will see how to find the power recursively in Carbon in detail. Let’s start going!

Finding power recursively in Carbon

Problem Statement

In this problem, we are given two numbers, a and b, inputted by the user, and we have to calculate a^b recursively in Carbon. We have to write a function in Carbon that estimates the power of a^b, taking two numbers, a and b, as input and returning the output.

Sample Examples

Let us take some examples to understand what our output should be when we take an input of two numbers.

Example 1:

Input:  3 2
Output: 9
Explanation: The power of 3^2 equals 9.

Example 2:

Input:  2 3
Output: 8
Explanation: The power of 2^3 is equal to 8.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

The approach of finding the power of numbers using Carbon is easy. We must write a function that will take two parameters, a, and b, and it will return the output using recursion. It will call the function till the value of b become equal to 0, or the value of a is equal to 0.

Algorithm

The following given steps are used to find the power of a number recursively using Carbon:-

1. Call the cal_power function with two parameters, a and b.

2. If at any time value of b become equal to zero, function cal_power will return 1.

3. If the value of a is equal to zero, then function cal_power will return 0 as a result.

4. The function will repeatedly call the same function while decreasing the value of b by one each time till the value of b becomes equal to zero.

5. The calculated value will then be returned to the function call in the main block.

dry run of power of number

Implementation

The program calculates the power of two numbers a^b as:-

package sample api;

fn cal_power(a: i32, b: i32) - > i32 {
    if (b == 0) {
        return 1;
    }

    if (a == 0) {
        return 0;
    }
    return a * cal_power(a, b - 1);
}

fn Main() - > i32 {
    return cal_power(2, 3);
}


Output:

Output

Time Complexity

The above approach's time complexity for finding the power recursively in Carbon is O(b)  because we have to perform the computation ‘b’ number of times.

Space Complexity

The above approach's space complexity for finding the power recursively in Carbon is O(1), as we did not use any extra space for storing values.

Read More - Time Complexity of Sorting Algorithms

Optimized Approach

The optimized approach of finding the power of a number recursively in Carbon is using divide and conqueror recursively.

Optimized Algorithm

The following given steps are used to calculate the power recursively using Carbon:-

1. Call the cal_power function with two parameters, a and b.

2. If at any time value of b become equal to zero, function cal_power will return 1.

3. If the value of b is even,  then it will return (a^(b/2))*(a^(b/2)).

4. If the value of b is odd,  then it will return (a*a^((b-1)/2))*(a^((b-1)/2)).

5. The calculated value will then be returned to the function call in the main block.

Dry run of Optimized Code

Optimized Implementation

The optimized program calculates the power of two numbers a^b as-.

package sample api;

fn cal_power(a: i32, b: i32) - > i32 {
    if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        return cal_power(a, b / 2) * cal_power(a, b / 2);
    }
    return a * cal_power(a, b / 2) * cal_power(a, b / 2);
}

fn Main() - > i32 {
    return cal_power(3, 5);
}


Output:

Output

Time Complexity

The above approach's time complexity for finding the power recursively in Carbon is O(log(b))  because we are doing one online computation in every level of the recursion sub-tree.

Space Complexity

The above approach's space complexity for finding the power recursively in Carbon is O(1), as we did not use any extra space for storing values.

Also check out - Rod Cutting Problem

Frequently Asked Questions

What is Recursion?

Recursion is the function calling itself either directly or indirectly, and the corresponding function is known as a recursive function.

Does recursion follow any rules?

A set of rules that calls itself with "smaller (or simpler)" enter values is known as a recursive set of rules. 

What is the recursive method?

A process or algorithm that uses loops to execute steps repeatedly is called recursive: A process or algorithm that uses itself repeatedly and with various arguments.

Name the different types of recursion.

There are six types of recursion, direct, indirect, tail, No tail, linear, and tree recursion.

What is the recursion tree method?

Recurrence relations can be resolved using the Recursion Tree Method. Recursive trees are created using this method from a recurrence relation. Each node represents the expense incurred at different recursive levels. The total cost is calculated by adding the costs from each level.

Conclusion

Congratulations on finishing the blog! We have finished reading the problem of finding the power recursively in Carbon.

We hope this blog has helped you enhance your knowledge regarding the topic of recursion and the basic mathematics approach. If you want to learn more, then you can check articles on:-

1. Jump Statements in Carbon

2. Program to find even or odd numbers using Carbon

3. Armstrong Number using Carbon
 

Please refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview bundle.

Happy learning!

Live masterclass