Simple power recursion console application

• Download Recrusion_-_Console.zip - 37 KB

This was developed on Visual Studio 2013, but you can just run the exe, or copy the code from the article into your own version and compile it. 

Introduction 

I gave an answer to a question on StackOverflow about recursion, and I wanted to link that to a simple visual animation. Giving Google a go, I couldn't find any animation that would portrait the recursion, so I've decided to write a simple console program to illustrate the process. 

The recursion topic is explained everywhere (have a look at Wikipedia, or Wolfarm which has a shorter version). What I wanted is to give the person asking or trying to figure out the recursion a visual aid. 

 This is what the result will look like (depending on your input), where each line is printed out after a short pause:

Using the code

Since this is a tutorial for beginners, the code is very straight forward, simple, and adhering to the principles of good programming (we wouldn't want to set a bad example now, wouldn't me?). 

 I'll explain each bit of the program, and paste the entire code at the end as well.

Let's dig straight in. First of all, we need to figure out what we want to do, and how to do it. The flow of events is rather simple:

1. Ask user for input (base and exponent)
2. Parse the input 
3. Call the recursive method if data is valid  
4. Display error message if input is invalid 
5. Display the steps (we'll do that as we go) 
6. Display final result if input was valid 

We will use this as our design, programming by intention, creating methods that have descriptive names, a sole purpose, have comments, and strive to have clean simple code.

The code is fully commented, so in most cases there's not more much to add to it. In real life, I wouldn't expect you to write so many comments. Use them to explain what you were thinking, or what is supposed to happen. You can skip obvious comments by using good names. For example, instead of writing:

var v = SomeMethodResult();   // v will hold height of our square

Go with:

int heightOfSquare = GetSquareHeight(); 

No comments needed. 

 Let's start: 

Main method: 

Quite simple and straight forward ... following the steps, we'll call the methods in the order we need them: 

static void Main(string[] args)
{
    // -------------------- The variables we'll use: ------------------
    int base_value, exponent ;
    int result = -1 ;           
 
    // -------------------- Following the steps : ---------------------

    // 1. Getting the input
    string input = GetInput();
 
    // 2. Parsing the input
    bool input_valid = ParseInput(input, out base_value, out exponent);
 
    // 3. Call the recursive method if data is valid 
    if (input_valid)
        result = Power(base_value, exponent);
 
    // 4. Display error message if input is invalid 
    else
        InvalidInput();
 
    // 6. Display final result (only in case the input was valid)
    if (input_valid)
        Console.Out.WriteLine(Environment.NewLine + "Final result:\t{0} = {1}", input, result);
 
    // Here we'll wait for the user to hit any key before we exit, so the screen 
    // won't disappear as soon as we're done
    Console.Out.WriteLine(Environment.NewLine + "Hit any key to quit.");
    Console.ReadKey();
} 

 1. Ask user for input  

// <summary>
/// Will let the user know what he needs to input and read that input.
/// </summary>
/// <returns>The string the user typed</returns>
private static string GetInput()
{
    // Output the message requesting the information
    Console.Out.WriteLine("Please enter the Power to calculate in this format: x^y "
      + Environment.NewLine + "(where x is the base, y is the exponent, and they are non negative ints)."
      + Environment.NewLine);
 
    //  Next line will read input until user hits the 'Enter' key
    var temp_string = Console.ReadLine();      
 
    return temp_string;
}  

2. Parse the Input 

/// <summary>
/// Calling this will parse the input we'll pass, and initialize the variables we'll use.
/// </summary>
/// <param name="input">The string the user typed in</param>
/// <param name="base_val">Reference for the base value</param>
/// <param name="exp">reference for the exponent</param>
/// <returns>True if the input was in the given pattern: X^Y , where X and Y are positive ints</returns>
private static bool ParseInput(string input, out int base_val, out int exp)
{
    base_val = 0;   // We need to initialize out parameters
    exp = 0;        // Otherwise, you'll get an error.

    // No input is obviously bad. Return false
    if (string.IsNullOrWhiteSpace(input))
    {
        Console.Out.WriteLine("Empty input is invalid");
        return false;
    }
 
    // Lets split the input on the '^' character
    var two_parts = input.Split('^');
 
    // If we have more than 2 parts, or less, return false.
    if (two_parts.Length != 2)
    {
        Console.Out.WriteLine("Wrong number of parameters give.");
        return false;
    }
 
    // Int32.TryParse takes a string, and an int variable it will fill if the parse is successful. 
    // If it fails, it returns false, and the variable won't be filled. The next line 
    // tries to fill both values by calling Int32.TryParse on both parts of our string.
    var valid_ints = (  Int32.TryParse(two_parts[0], out base_val) 
                        && Int32.TryParse(two_parts[1], out exp)      );
 
    // If the TryParse on one (or both) of the strings failed. Return False
    if (!valid_ints)
    {
        Console.Out.WriteLine("Base or Exponent (or both) were not valid ints.");
        return false;
    }
 
    // Ruling out negative numbers
    if (base_val <0 || exp <0)
    {
        Console.Out.WriteLine("Base and Exponent must be positive.");
        return false;
    }
 
    // End case, all is valid. Return true
    return true;
} 

Yes, this could have be done in a shorter way, but I prefer clarity to brevity.

At any point, if we know the input is invalid, we'll output an error message and return false. It won't save much time in this method, but if you have calls to methods that might take a long time to calculate instead of simple checks, this will save you time by returning without going any further than needed.

At the end of the method, we return true, since we covered all the failures before that point (another option around this is to have a Boolean variable that we can set to true/false, and return it once in the end).  

3. Call the recursive method if data is valid  (includes step 5) 

This is where the interesting bit happen. As this is a recursive method, it will call itself over and over until it hits the base condition, and then role back up, returning the value set in the base condition. 

If you won't set the base condition, you'll eventually run out of memory, since the program will keep calling itself over and over again, which is (obviously) not good.

Our base condition is a call to Power with exponent = 0, in which case we'll return 1. In any other case, we'll call the Power again, with the same base, and a smaller exponent.

/// <summary>
/// Recursive call to calculate Power x^y
/// </summary>
/// <param name="base_value">The base</param>
/// <param name="exponent">The exponent</param>
/// <param name="padding">Padding, for output.</param>
/// <returns></returns>
private static int Power(int base_value, int exponent, string padding = "")
{
    // 5. Display the steps
    Console.Out.WriteLine(string.Format("{2}Power called with: {0}^{1}", base_value, exponent, padding));
    Thread.Sleep(750);
 
    if (exponent == 0)
    {
        // 5. Display the steps
        Console.Out.WriteLine("{0}{1}Base case reached, returning 1.{0}", Environment.NewLine, padding);
        return 1;
    }
    else
    {
        // THIS IS WHERE THE RECURSION HAPPENS.  we call ourselves with a different argument.
        var return_value = base_value * Power(base_value, exponent - 1, padding + "  ");
 
        // 5. Display the steps
        Console.Out.WriteLine("{0}Going back in the recursion, returning {1}.", padding, return_value);
        Thread.Sleep(750);
        return return_value;
    }
} 

Notice that I've added a string argument, in order to pad the output. This is not required, but it lets us visualize the output better, and also introduce beginners to Named and Optional arguments . To sum it up, if you call your method without that parameter (the 3rd one in our case), it will get the default value assigned in the method definition (in our case, an empty string). 

Also notice that you can use named (well, numbered) parameters inside the String.Format() call, in which {0} will be replaced with the first argument after the string, {1} with the second, and so on. Notice that I can write them out of order in the string, for example:  "{2} something {1} ..."  and they don't need to appear in the order of appearance at the end. 

In case you're wondering, the Thread.Sleep(750); will simply make the program wait 0.75 seconds (750 milliseconds) before continuing. You can play with this value as you wish, I found it to be about right for my purposes. 

4. Display error message if input is invalid   

This will simply write out the obvious in this case, and return nothing. There's not much point to this in this specific case, but in a "real world" application, you might want to do other things if the input was invalid. 

/// <summary>
/// Informs user about bad input. 
/// </summary>
private static void InvalidInput()
{
    Console.Out.WriteLine(Environment.NewLine + "Invalid input. Have a good day.");
    return;
} 

Wrapping up 

Step 5 was taken care of during step 3, and step 6 is just an output to show the result.

If you would code this for something, you would probably avoid all the outputs inside the recursive call, and it would look like :

private static int Power(int base_value, int exponent)
{
    if (exponent == 0)
        return 1;
    else
        return = base_value * Power(base_value, exponent-1);
}

Points of Interest

I tried to be as verbose as possible and explain this in a way that will be informative to a beginner . In real life you could achieve the same with less code and comments, avoid calls to methods, and so on. Since my target audience is beginners, I would suggest adopting this good programming habits. It'll save you hours of debugging in the future :)

Please rate and comment if you've found this useful / or have any questions.

Complete code (just paste and run)

using System;
using System.Threading;

namespace Recursion_Console
{
    class Program
    {
        static void Main(string[] args)
        {
            // -------------------- The variables we'll use: ------------------
            int base_value, exponent ;
            int result = -1 ;           

            // -------------------- Following the steps : ---------------------

            // 1. Getting the input
            string input = GetInput();

            // 2. Parsing the input
            bool input_valid = ParseInput(input, out base_value, out exponent);

            // 3. Call the recursive method if data is valid 
            if (input_valid)
                result = Power(base_value, exponent);

            // 4. Display error message if input is invalid 
            else
                InvalidInput();

            // 6. Display final result (only in case the input was valid)
            if (input_valid)
                Console.Out.WriteLine(Environment.NewLine + 
                  "Final result:\t{0} = {1}", input, result);

            // Here we'll wait for the user to hit any key before we exit, so the screen 
            // won't disappear as soon as we're done
            Console.Out.WriteLine(Environment.NewLine + "Hit any key to quit.");
            Console.ReadKey();
        }

        /// <summary>
        /// Recursive call to calculate Power x^y
        /// </summary>
        /// <param name="base_value">The base</param>
        /// <param name="exponent">The exponent</param>
        /// <param name="padding">Padding, for output.</param>
        /// <returns></returns>
        private static int Power(int base_value, int exponent, string padding = "")
        {
            // 5. Display the steps
            Console.Out.WriteLine(
              string.Format("{2}Power called with: {0}^{1}", base_value, exponent, padding));
            Thread.Sleep(750);

            if (exponent == 0)
            {
                // 5. Display the steps
                Console.Out.WriteLine("{0}{1}Base case reached, returning 1.{0}", Environment.NewLine, padding);
                return 1;
            }
            else
            {
                // THIS IS WHERE THE RECURSION HAPPENS.  we call ourselves with a different argument.
                var return_value = base_value * Power(base_value, exponent - 1, padding + "  ");

                // 5. Display the steps
                Console.Out.WriteLine("{0}Going back in the recursion, returning {1}.", padding, return_value);
                Thread.Sleep(750);
                return return_value;
            }
        }

        /// <summary>
        /// Informs user about bad input. 
        /// </summary>
        private static void InvalidInput()
        {
            Console.Out.WriteLine(Environment.NewLine + "Invalid input. Have a good day.");
            return;
        }

        /// <summary>
        /// Will let the user know what he needs to input and read that input.
        /// </summary>
        /// <returns>The string the user typed</returns>
        private static string GetInput()
        {
            // Output the message requesting the information
            Console.Out.WriteLine("Please enter the Power to calculate in this format: x^y "
              + Environment.NewLine 
              + "(where x is the base, y is the exponent, and they are non negative ints)."
              + Environment.NewLine);

            //  Next line will read input until user hits the 'Enter' key
            var temp_string = Console.ReadLine();      

            return temp_string;
        }

        /// <summary>
        /// Calling this will parse the input we'll pass, and initialize the variables we'll use.
        /// </summary>
        /// <param name="input">The string the user typed in</param>
        /// <param name="base_val">Reference for the base value</param>
        /// <param name="exp">reference for the exponent</param>
        /// <returns>True if the input was in the given
        ///       pattern: X^Y , where X and Y are positive ints</returns>
        private static bool ParseInput(string input, out int base_val, out int exp)
        {
            base_val = 0;   // We need to initialize  out parameters
            exp = 0;        // Otherwise, you'll get an error.

            // No input is obviously bad. Return false
            if (string.IsNullOrWhiteSpace(input))
            {
                Console.Out.WriteLine("Empty input is invalid");
                return false;
            }

            // Lets split the input on the '^' character
            var two_parts = input.Split('^');

            // If we have more than 2 parts, or less, return false.
            if (two_parts.Length != 2)
            {
                Console.Out.WriteLine("Wrong number of parameters give.");
                return false;
            }

            // Int32.TryParse takes a string, and an int variable it will fill if the parse is successful. 
            // If it fails, it returns false, and the variable won't be filled. The next line 
            // tries to fill both values by calling Int32.TryParse on both parts of our string.
            var valid_ints = (  Int32.TryParse(two_parts[0], out base_val) 
                                && Int32.TryParse(two_parts[1], out exp)      );

            // If the TryParse on one (or both) of the strings failed. Return False
            if (!valid_ints)
            {
                Console.Out.WriteLine("Base or Exponent (or both) were not valid ints.");
                return false;
            }

            // Ruling out negative numbers
            if (base_val <0 || exp <0)
            {
                Console.Out.WriteLine("Base and Exponent must be positive.");
                return false;
            }

            // End case, all is valid. Return true
            return true;
        }

    }
}

History

• November 16th, initial release.