C#递归函数详细介绍及使⽤⽅法
什么是递归函数/⽅法？
任何⼀个⽅法既可以调⽤其他⽅法也可以调⽤⾃⼰，⽽当这个⽅法调⽤⾃⼰时，我们就叫它递归函数或递归⽅法。
通常递归有两个特点：
1. 递归⽅法⼀直会调⽤⾃⼰直到某些条件被满⾜
2. 递归⽅法会有⼀些参数，⽽它会把⼀些新的参数值传递给⾃⼰。
那什么是递归函数？函数和⽅法没有本质区别，但函数仅在类的内部使⽤。以前C#中只有⽅法，从.NET 3.5开始才有了匿名函数。
所以，我们最好叫递归⽅法，⽽⾮递归函数，本⽂中将统⼀称之为递归。
在应⽤程序中为什么要使⽤递归？何时使⽤递归？如何⽤？
“写任何⼀个程序可以⽤赋值和if-then-else语句表⽰出来，⽽while语句则可以⽤赋值、if-then-else和递归
表⽰出来。”（出⾃Ellis Horowitz的《数据结构基础（C语⾔版）》 - Fundamentals of Data Structure in C）
递归解决⽅案对于复杂的开发来说很⽅便，⽽且⼗分强⼤，但由于频繁使⽤调⽤栈（call stack）可能会引起性能问题（有些时候性能极差）。
调⽤栈图⽰
下⾯我打算介绍⼀些例⼦来帮助你更好的理解递归的风险和回报。
1. 阶乘
阶乘（!）是⼩于某个数的所有正整数的乘积。
0! = 1
1! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
...
n! = n * (n - 1)!
下⾯是计算阶乘的⼀种实现⽅法（没有递归）：
public long Factorial(int n)
{
if (n == 0)
return 1;
long value = 1;
for (int i = n; i > 0; i--)
{
value *= i;
}
return value;
}
下⾯是⽤递归的⽅法实现计算阶乘，与之前的代码⽐起来它更简洁。
public long Factorial(int n)
{
if (n == 0)//限制条件，对该⽅法调⽤⾃⼰做了限制
return 1;
return n * Factorial(n - 1);
}
你知道的，n的阶乘实际上是n-1的阶乘乘以n，且n>0。
它可以表⽰成 Factorial(n) = Factorial(n-1) * n
这是⽅法的返回值，但我们需要⼀个条件
如果 n=0 返回1。
现在这个程式的逻辑应该很清楚了，这样我们就能够轻易的理解。
2. Fibonacci数列
Fibonacci数列是按以下顺序排列的数字：
0,1,1,2,3,5,8,13,21,34,55,…如果F0 = 0 并且 F1= 1 那么Fn = Fn-1 + Fn-2
下⾯的⽅法就是⽤来计算Fn的（没有递归，性能好）
public long Fib(int n)
{
if (n < 2)
return n;
long[] f = new long[n+1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++)
{
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
如果我们使⽤递归⽅法，这个代码将更加简单，但性能很差。
复制代码代码如下:
public long Fib(int n)
{
if (n == 0 || n == 1) //满⾜条件
return n;
return Fib(k - 2) + Fib(k - 1);
}
<STRONG><SPAN >3. 布尔组合</SPAN></STRONG>
有时我们需要解决的问题⽐Fibonacci数列复杂很多，例如我们要枚举所有的布尔变量的组合。换句话说，如果n=3，那么我们必须输出如下结果：
true, true, true
true, true, false
true, false, true
true, false, false
false, true, true
false, true, false
false, false, true
false, false, false如果n很⼤，且不⽤递归是很难解决这个问题的。
复制代码代码如下:
public void CompositionBooleans(string result, int counter)
{
if (counter == 0)
return;
bool[] booleans = new bool[2] { true, false };
for (int j = 0; j < 2; j++)
{
StringBuilder stringBuilder = new StringBuilder(result);
stringBuilder.Append(string.Format("{0} ", booleans[j].ToString())).ToString();
if (counter == 1)
Console.WriteLine(stringBuilder.ToString());
CompositionBooleans(stringBuilder.ToString(), counter - 1);
}
}
现在让我们来调⽤上⾯这个⽅法：
CompositionBoolean(string.Empty, 3);
Ian Shlasko建议我们这样使⽤递归：
public void BooleanCompositions(int count)
{
BooleanCompositions(count - 1, "true");
BooleanCompositions(count - 1, "false");
}
private void BooleanCompositions(int counter, string partialOutput)
{
if (counter <= 0)
Console.WriteLine(partialOutput);
else
{
BooleanCompositions(counter - 1, partialOutput+ ", true");
BooleanCompositions(counter - 1, partialOutput+ ", false");
}
}
4. 获取内部异常
如果你想获得innerException，那就选择递归⽅法吧，它很有⽤。
public Exception GetInnerException(Exception ex)
{
return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException);
}
为什么要获得最后⼀个innerException呢？！这不是本⽂的主题，我们的主题是如果你想获得最⾥⾯的innerException，你可以靠递归⽅法来完成。
这⾥的代码：
return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException);
与下⾯的代码等价
if (ex.InnerException == null)//限制条件
return ex;
return GetInnerException(ex.InnerException);//⽤内部异常作为参数调⽤⾃⼰
现在，⼀旦我们获得了⼀个异常，我们就能到最⾥⾯的innerException。例如：
try
{
throw new Exception("This is the exception",
new Exception("This is the first inner exception.",
new Exception("This is the last inner exception.")));
}
catch (Exception ex)
{
Console.WriteLine(GetInnerException(ex).Message);
}
我曾经想写关于匿名递归⽅法的⽂章，但是我发觉我的解释⽆法超越那篇⽂章。
5. 查⽂件
我在供你下载的⽰范项⽬中使⽤了递归，通过这个项⽬你可以搜索某个路径，并获得当前⽂件夹和其
⼦⽂件夹中所有⽂件的路径。private Dictionary<string, string> errors = new Dictionary<string, string>();
private List<string> result = new List<string>();
private void SearchForFiles(string path)
{
try
{
foreach (string fileName in Directory.GetFiles(path))//Gets all files in the current path
{
result.Add(fileName);
}
foreach (string directory in Directory.GetDirectories(path))//Gets all folders in the current path
{
SearchForFiles(directory);//The methods calls itself with a new parameter, here!writeline函数
}
}
catch (System.Exception ex)
{
errors.Add(path, ex.Message);//Stores Error Messages in a dictionary with path in key
}
}
这个⽅法似乎不需要满⾜任何条件，因为每个⽬录如果没有⼦⽬录，会⾃动遍历所有⼦⽂件。
总结
我们其实可以⽤递推算法来替代递归，且性能会更好些，但我们可能需要更多的时间开销和⾮递归函数。但关键是我们必须根据场景选择最佳实现⽅式。
James MaCaffrey博⼠认为尽量不要使⽤递归，除⾮实在没有办法。你可以读⼀下他的⽂章。
我认为：
A) 如果性能是⾮常重要的，请避免使⽤递归
B)如果递推⽅式不是很复杂的，请避免使⽤递归
C) 如果A和B都不满⾜，请不要犹豫，⽤递归吧。
例如：
第⼀节（阶乘）：这⾥⽤递推并不复杂，那么就避免⽤递归。
第⼆节（Fibonacci）：像这样的递归并不被推荐。
当然，我并不是要贬低递归的价值，我记得⼈⼯智能中的重要⼀章有个极⼩化极⼤算法（Minimax algorithm），全部是⽤递归实现的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。