Finding Power Recursively in Carbon

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.

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.

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.

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 DSA, Competitive Programming, JavaScript, System 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!