简单的幂递归控制台应用程序
一个简单的控制台应用程序，用于可视化和理解递归
这是用 Visual Studio 2013 开发的，但你也可以直接运行 exe 文件，或者将文章中的代码复制到你自己的版本中进行编译。
介绍
我在 StackOverflow 上对一个关于递归的 问题 进行了 回答，我想将其链接到一个简单的可视化动画。在尝试用 Google 搜索时，我没有找到任何可以展示递归的动画，所以我决定编写一个简单的控制台程序来演示这个过程。
递归的主题在各种地方都有解释（可以看看 维基百科，或者 Wolfram Alpha，它有一个简短的版本）。我想要的是为提问者或正在尝试理解递归的人提供一个视觉辅助工具。
结果会是这样的（取决于你的输入），每一行会在短暂的暂停后打印出来。
使用代码
由于这是一个面向初学者的教程，代码非常直接、简单，并且遵循了良好编程的原则（我们不想树立一个坏榜样，对吧？）。
我将解释程序的每一部分，并在最后粘贴完整的代码。
让我们直接开始。首先，我们需要弄清楚我们想要做什么，以及如何去做。事件流程相当简单：
- 向用户询问输入（基数和指数）
- 解析输入
- 如果数据有效，则调用递归方法
- 如果输入无效，则显示错误消息
- 显示步骤 （我们将边做边完成）
- 如果输入有效，则显示最终结果
我们将使用 意图驱动编程 作为我们的设计方法，创建具有描述性名称、单一目的、带有注释并力求代码简洁的方法。
代码已完全注释，所以在大多数情况下不需要添加更多内容。在实际生活中，我不期望你写这么多注释。使用注释来解释你的想法或预期发生的事情。你可以通过使用好的名称来跳过显而易见的注释。例如，不要写：
var v = SomeMethodResult(); // v will hold height of our square选择
int heightOfSquare = GetSquareHeight(); 无需注释。
我们开始吧：
Main 方法：
非常简单直接……按照步骤，我们将按所需顺序调用方法：
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. 向用户询问输入
// <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. 解析输入
/// <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;
}
是的，这可以用更短的方式完成，但我更喜欢清晰而不是简洁。
在任何时候，如果我们知道输入无效，我们将输出一条错误消息并返回 false。在这个方法中节省不了多少时间，但如果你调用的是可能需要很长时间才能计算出的方法，而不是简单的检查，那么通过在必要时提前返回，就可以节省时间。
在该方法的末尾，我们返回 true，因为我们已经处理了之前的所有失败情况（另一种选择是使用一个布尔变量，我们可以将其设置为 true/false，并在最后返回它）。
3. 如果数据有效，则调用递归方法 （包括步骤 5）
这是有趣的部分。由于这是一个递归方法，它会一遍又一遍地调用自身，直到达到基本条件，然后逐层返回，返回基本条件中设置的值。
如果你不设置基本条件，你最终会耗尽内存，因为程序会不断地调用自己，这（显然）是不好的。
我们的基本条件是对 `Power` 方法的调用，当 `exponent = 0` 时，我们将返回 `1`。在任何其他情况下，我们将再次调用 `Power` 方法，使用相同的基数和一个更小的指数。
/// <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;
}
} 请注意，我添加了一个字符串参数，用于填充输出。这不是必需的，但它让我们更好地可视化输出，并且还可以向初学者介绍 命名和可选参数 。总而言之，如果你在调用方法时没有该参数（在本例中是第三个参数），它将获得方法定义中分配的默认值（在本例中为空字符串）。
另外请注意，你可以在 `String.Format()` 调用中使用命名（或者说是编号）参数，其中 {0} 将被第一个字符串后的参数替换，{1} 被第二个替换，依此类推。请注意，我可以在字符串中以不同的顺序书写它们，例如："{2} 某事 {1} ..." 它们不必按末尾出现的顺序排列。
如果你好奇的话，`Thread.Sleep(750);` 将使程序在继续之前等待 0.75 秒（750 毫秒）。你可以随意更改此值，我发现它对我来说大约合适。
4. 如果输入无效，则显示错误消息
在这种情况下，它只会写出显而易见的内容，并且不返回任何内容。在这种特定情况下，这没什么意义，但在“现实世界”应用程序中，你可能希望在输入无效时执行其他操作。
/// <summary>
/// Informs user about bad input.
/// </summary>
private static void InvalidInput()
{
Console.Out.WriteLine(Environment.NewLine + "Invalid input. Have a good day.");
return;
} 总结
步骤 5 已在步骤 3 中处理，步骤 6 只是一个显示结果的输出。
如果你是为某个实际目的编写此代码，你可能会避免在递归调用中进行所有输出，它看起来会是这样的：
private static int Power(int base_value, int exponent)
{
if (exponent == 0)
return 1;
else
return = base_value * Power(base_value, exponent-1);
}
关注点
我尽量做到详尽，并以一种对初学者有信息量的方式来解释。在实际生活中，你可以用更少的代码和注释来实现相同的功能，避免调用方法等等。由于我的目标受众是初学者，我建议采纳这些良好的编程习惯。这将在未来为你节省数小时的调试时间：)
如果你觉得这有帮助/有任何疑问，请评分和评论。
完整代码（直接复制粘贴即可运行）
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;
}
}
}
历史
- 11月16日，初次发布。