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:
- Ask user for input (base and exponent)
- Parse the input
- Call the recursive method if data is valid
- Display error message if input is invalid
- Display the steps (we'll do that as we go)
- 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();
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)
{
int base_value, exponent ;
int result = -1 ;
string input = GetInput();
bool input_valid = ParseInput(input, out base_value, out exponent);
if (input_valid)
result = Power(base_value, exponent);
else
InvalidInput();
if (input_valid)
Console.Out.WriteLine(Environment.NewLine + "Final result:\t{0} = {1}", input, result);
Console.Out.WriteLine(Environment.NewLine + "Hit any key to quit.");
Console.ReadKey();
}
1. Ask user for input
private static string GetInput()
{
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);
var temp_string = Console.ReadLine();
return temp_string;
}
2. Parse the Input
private static bool ParseInput(string input, out int base_val, out int exp)
{
base_val = 0;
exp = 0;
if (string.IsNullOrWhiteSpace(input))
{
Console.Out.WriteLine("Empty input is invalid");
return false;
}
var two_parts = input.Split('^');
if (two_parts.Length != 2)
{
Console.Out.WriteLine("Wrong number of parameters give.");
return false;
}
var valid_ints = ( Int32.TryParse(two_parts[0], out base_val)
&& Int32.TryParse(two_parts[1], out exp) );
if (!valid_ints)
{
Console.Out.WriteLine("Base or Exponent (or both) were not valid ints.");
return false;
}
if (base_val <0 || exp <0)
{
Console.Out.WriteLine("Base and Exponent must be positive.");
return false;
}
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.
private static int Power(int base_value, int exponent, string padding = "")
{
Console.Out.WriteLine(string.Format("{2}Power called with: {0}^{1}", base_value, exponent, padding));
Thread.Sleep(750);
if (exponent == 0)
{
Console.Out.WriteLine("{0}{1}Base case reached, returning 1.{0}", Environment.NewLine, padding);
return 1;
}
else
{
var return_value = base_value * Power(base_value, exponent - 1, padding + " ");
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.
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)
{
int base_value, exponent ;
int result = -1 ;
string input = GetInput();
bool input_valid = ParseInput(input, out base_value, out exponent);
if (input_valid)
result = Power(base_value, exponent);
else
InvalidInput();
if (input_valid)
Console.Out.WriteLine(Environment.NewLine +
"Final result:\t{0} = {1}", input, result);
Console.Out.WriteLine(Environment.NewLine + "Hit any key to quit.");
Console.ReadKey();
}
private static int Power(int base_value, int exponent, string padding = "")
{
Console.Out.WriteLine(
string.Format("{2}Power called with: {0}^{1}", base_value, exponent, padding));
Thread.Sleep(750);
if (exponent == 0)
{
Console.Out.WriteLine("{0}{1}Base case reached, returning 1.{0}", Environment.NewLine, padding);
return 1;
}
else
{
var return_value = base_value * Power(base_value, exponent - 1, padding + " ");
Console.Out.WriteLine("{0}Going back in the recursion, returning {1}.", padding, return_value);
Thread.Sleep(750);
return return_value;
}
}
private static void InvalidInput()
{
Console.Out.WriteLine(Environment.NewLine + "Invalid input. Have a good day.");
return;
}
private static string GetInput()
{
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);
var temp_string = Console.ReadLine();
return temp_string;
}
private static bool ParseInput(string input, out int base_val, out int exp)
{
base_val = 0;
exp = 0;
if (string.IsNullOrWhiteSpace(input))
{
Console.Out.WriteLine("Empty input is invalid");
return false;
}
var two_parts = input.Split('^');
if (two_parts.Length != 2)
{
Console.Out.WriteLine("Wrong number of parameters give.");
return false;
}
var valid_ints = ( Int32.TryParse(two_parts[0], out base_val)
&& Int32.TryParse(two_parts[1], out exp) );
if (!valid_ints)
{
Console.Out.WriteLine("Base or Exponent (or both) were not valid ints.");
return false;
}
if (base_val <0 || exp <0)
{
Console.Out.WriteLine("Base and Exponent must be positive.");
return false;
}
return true;
}
}
}
History
- November 16th, initial release.