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!

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.

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:

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.

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.

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:

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.

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:-