C# 递归函数详细介绍及使用方法
程序员文章站
2024-03-04 20:40:06
什么是递归函数/方法？ 任何一个方法既可以调用其他方法也可以调用自己，而当这个方法调用自己时，我们就叫它递归函数或递归方法。 通常递归有两个特点： 1. 递归方法一直会调用...
什么是递归函数/方法？
任何一个方法既可以调用其他方法也可以调用自己，而当这个方法调用自己时，我们就叫它递归函数或递归方法。
通常递归有两个特点：
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 style="font-size: medium">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!
}
}
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），全部是用递归实现的。
但是如果你决定使用队规方法，你最好尝试用存储来优化它。
版权声明：本文由作者tony qu原创， 未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则视为侵权。
任何一个方法既可以调用其他方法也可以调用自己，而当这个方法调用自己时，我们就叫它递归函数或递归方法。
通常递归有两个特点：
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 style="font-size: medium">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!
}
}
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），全部是用递归实现的。
但是如果你决定使用队规方法，你最好尝试用存储来优化它。
版权声明：本文由作者tony qu原创， 未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则视为侵权。
上一篇： Java跨域问题的处理详解