14,297,239 members

# Simple power recursion console application

Rate this:
16 Nov 2013CPOL
A simple console application to visualize and understand recursion

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(); `

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.");
} ```

```// <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

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>
/// <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));

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);
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>
/// </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;

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.");
}

/// <summary>
/// Recursive call to calculate Power x^y
/// </summary>
/// <param name="base_value">The base</param>
/// <param name="exponent">The exponent</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));

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);
return return_value;
}
}

/// <summary>
/// </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

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.

## Share

 Software Developer Australia
Coding since I Remember myself ... went through Basic on Commodore 64 to C# on an 8 core i7... In between worked with c, c++, java, assembler, php, pascal, JScript, SQL based DB's and a bit of NoSQL as well.

Love software, and I'm usually fidgeting around with technology software and hardware on my free time.

 First Prev Next
 Problem Similar to this one Member 1082870519-May-14 1:47 Member 10828705 19-May-14 1:47
 Re: Problem Similar to this one _Noctis_19-May-14 2:09 _Noctis_ 19-May-14 2:09
 Last Visit: 14-Sep-19 21:38     Last Update: 14-Sep-19 21:38 Refresh 1