using System;

​

public class Program

{

    public static void Main()

    {

        //displayPower(3, 0);

        //displayPower(3, 1);

        //displayPower(3, 2);

        //displayPower(3, -1);

        displayPower(3, -5);

        //displayPower(3, -3);

        //displayPower(5,-10);

        //displayPower(5,20);

        //displayPower(5,-20);

    }

​

    static bool isEven(int n)

    {

        return n % 2 == 0;

    }

​

    static bool isOdd(int n)

    {

        return !isEven(n);

    }

​

    static double power(int x, int n)

    {

        //Console.WriteLine("Computing " + x + " raised to power " + n + ".");

        // base case

        if (n == 0)

        {

            return 1;

        }

​

        // recursive case: n is negative 

        if (n < 0)

        {

            Console.WriteLine(n);

            return 1 / power(x, -n);

        }

​

        // recursive case: n is odd

        if (isOdd(n))

        {

            Console.WriteLine(n);

            return power(x, n - 1) * x;

        }

​

        // recursive case: n is even

        if (isEven(n))

        {

            Console.WriteLine(n);

            var y = power(x, n / 2);

            return y * y;

        }

​

        return 0;

    }

​

    static void displayPower(int x, int n)

    {

        Console.WriteLine(x + " to the " + n + " is " + power(x, n));

    }

}