服务器之家

服务器之家 > 正文

C# 递归函数详细介绍及使用方法

时间:2019-10-14 11:52     来源/作者: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)可能会引起性能问题(有些时候性能极差)。 
我们来看一看下面这个图: 
C# 递归函数详细介绍及使用方法 
调用栈图示 
下面我打算介绍一些例子来帮助你更好的理解递归的风险和回报。 
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. 查找文件 
C# 递归函数详细介绍及使用方法
我在供你下载的示范项目中使用了递归,通过这个项目你可以搜索某个路径,并获得当前文件夹和其子文件夹中所有文件的路径。 

复制代码代码如下:


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原创, 未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则视为侵权。

标签:

相关文章

热门资讯

玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情 2019-06-22
抖音撒撒累累是什么歌 撒撒累累张艺兴歌曲名字
抖音撒撒累累是什么歌 撒撒累累张艺兴歌曲名字 2019-06-05
超A是什么意思 你好a表达的是什么
超A是什么意思 你好a表达的是什么 2019-06-06
返回顶部