Recursive Exponential Function


Write a 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


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.


Here is the code in C#

using System;

//Test class
class Test
    public Test()

    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)
            int y = RecursiveExp(x, n - 1);
            return x * y;

//Main class
class Program
    static void Main(string[] args)
        //Create a test object
        Test tst = new Test();

        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));
Search Terms...

Comments are closed.