Recursive Exponential Function

Share on Facebook
Share on LinkedIn
Bookmark this on Google Bookmarks
Bookmark this on Yahoo Bookmark
Bookmark this on Digg
Bookmark this on Livedoor Clip
Share on FriendFeed

Problem

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

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#

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

Comments are closed.