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

(0)

相关推荐

  • C#实现向函数传递不定参数的方法

    本文实例讲述了C#实现向函数传递不定参数的方法.分享给大家供大家参考.具体实现方法如下: using System; class Min{ public int MinVla(params int [] nums){ int m; if (nums.Length == 0){ Console.WriteLine("Error: no arguments."); return 0; } m = nums[0]; foreach ( int val in nums){ if ( val &

  • C#生成MD5的函数代码

    复制代码 代码如下: public static string GetMD5(string sDataIn)        {            MD5CryptoServiceProvider md5 = new MD5CryptoServiceProvider();            byte[] bytValue, bytHash;            bytValue = System.Text.Encoding.UTF8.GetBytes(sDataIn);         

  • C# Base64编码函数

    一. Base64的编码规则        Base64编码的思想是是采用64个基本的ASCII码字符对数据进行重新编码.它将需要编码的数据拆分成字节数组.以3个字节为一组.按顺序排列24 位数据,再把这24位数据分成4组,即每组6位.再在每组的的最高位前补两个0凑足一个字节.这样就把一个3字节为一组的数据重新编码成了4个字节.当所要编码的数据的字节数不是3的整倍数,也就是说在分组时最后一组不够3个字节.这时在最后一组填充1到2个0字节.并在最后编码完成后在结尾添加1到2个 "=".

  • C#常见应用函数实例小结

    本文实例总结了C#常见应用函数.分享给大家供大家参考,具体如下: 1.页面写CS代码(代码内嵌) <%@ Import Namespace="System" %> <%@ Import Namespace="System.Collections.Generic" %> <Script runat="server"> public int userId = 0; protected void Page_Load(

  • C# 静态构造函数使用总结

    •静态构造函数既没有访问修饰符,也没有参数. •如果没有编写静态构造函数,而这时类中包含带有初始值设定的静态字段,那么编译器会自动生成默认的静态构造函数. •在创建第一个类实例或任何静态成员被引用时,.NET将自动调用静态构造函数来初始化类,也就是说我们无法直接调用静态构造函数,也就无法控制什么时候执行静态构造函数了. •如果类中包含用来开始执行的 Main 方法,则该类的静态构造函数将在调用 Main 方法之前执行. •如果类中的静态字段带有初始化,则静态字段的初始化语句将在静态构造函数之前运

  • c#中DateTime.Now函数的使用详解

    复制代码 代码如下: //2008年4月24日     System.DateTime.Now.ToString("D");     //2008-4-24     System.DateTime.Now.ToString("d");     //2008年4月24日 16:30:15     System.DateTime.Now.ToString("F");     //2008年4月24日 16:30     System.DateTime

  • C#版的 Escape() 和 Unescape() 函数分享

    Escape: 复制代码 代码如下: public static string Escape(string str) { StringBuilder sb = new StringBuilder(); foreach (char c in str) { sb.Append((Char.IsLetterOrDigit(c) || c == '-' || c == '_' || c == '\\' || c == '/' || c == '.') ? c.ToString() : Uri.HexEs

  • C#字符串的截取函数用法总结

    本文实例总结了C#常用的字符串截取函数用法.分享给大家供大家参考.具体分析如下: 在C#中字符串截取函数包括有substring 函数,Remove 函数,indexOf 函数,它们三个都可以对字符串进行截取操作,下面我们来分别介绍一下. 下面是截取字符串过程中我们必须知道的以下函数:substring 函数.Remove 函数.indexOf函数. substring 函数: 返回第一个参数中从第二个参数指定的位置开始.第三个参数指定的长度的子字符串. 如果未指定第三个参数,将返回从第二个参数

  • C#实现为类和函数代码自动添加版权注释信息的方法

    本文实例讲述了C#实现为类和函数代码自动添加版权注释信息的方法,分享给大家供大家参考之用.具体方法如下: 以web项目为例: 一:给类加注释 1.在visual studio 的安装路径下 如:[盘符]:/Program files/Microsoft Visual Studio 8/Common7/IDE/ItemTemplates/web/cshare/2052/class.zip ,将里面的class.cs改为: /*------------------------------------

  • C#自定义函数NetxtString生成随机字符串

    本文实例展示了C#自定义函数NetxtString实现生成随机字符串的方法,在进行C#项目开发中非常实用!分享给大家供大家参考. 一.生成随机字符串 关键代码如下: /// <summary> /// 生成随机字符串 /// </summary> /// <param name="random">Random</param> /// <param name="size">字符串长度</param>

  • C# 常用日期时间函数(老用不熟)

    --DateTime 数字型 System.DateTime currentTime=new System.DateTime(); 1.1 取当前年月日时分秒 currentTime=System.DateTime.Now; 1.2 取当前年 int 年=currentTime.Year; 1.3 取当前月 int 月=currentTime.Month; 1.4 取当前日 int 日=currentTime.Day; 1.5 取当前时 int 时=currentTime.Hour; 1.6 取

  • C# 使用匿名函数解决EventHandler参数传递的难题

    首先,动态生成PictureBox,很简单, PictureBox box = new PictureBox() ; box.ImageLocation = imageRoad ; 其次,给PictureBox添加右键菜单,也不难, ContextMenu menu = new ContextMenu(); box.ContextMenu = menu ; 然后,要给右键菜单增加"删除"项,并实现删除图片事件.这个,比较麻烦. MenuItem item = new MenuItem(

随机推荐