Recursive Exponential Function
Problem
Write a recursive function to compute (x) to the power of (n) where (x) and (n) are positive integers. Your algorithm should run in O(logn) time complexity
Solution
Use divide and conquer technique. For even values of (n) calculate x^(n/2) and return the square of that as the final result because x^n = x^(n/2) * x^(n/2). For odd values of (n) calculate x^(n-1) and return it multiplied by (x) because x^n = x * x^(n-1). The first base case for recursion is n = 0 in this case you return 1. The second base case for recursion is n = 1 in this case you return (x). This algorithm runs in O(logn) because the problem size (n) is divided by (2) every time we call the recursive function. For odd values of (n) one extra call is executed before the number becomes even again which does not impact the overall performance of the algorithm for large values of (n). Please take a look at the code below for more details.
Code
Here is the code in C#
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
//Imports using System; //Test class class Test { //Constructor public Test() { //Nothing } public int RecursiveExp(int x, int n) { //First base case if (n == 0) { return 1; } //Second base case if (n == 1) { return x; } //Even values of (n) if (n % 2 == 0) { int y = RecursiveExp(x, n / 2); return y * y; } //Odd values of (n) else { int y = RecursiveExp(x, n - 1); return x * y; } } } //Main class class Program { //Main static void Main(string[] args) { //Create a test object Test tst = new Test(); //Examples Console.Out.WriteLine(tst.RecursiveExp(2, 0)); Console.Out.WriteLine(tst.RecursiveExp(2, 1)); Console.Out.WriteLine(tst.RecursiveExp(2, 3)); Console.Out.WriteLine(tst.RecursiveExp(2, 4)); } } |
About Author
Mohammed Abualrob
Software Engineer @ Cisco