用C#实现递归方法

2024-11-14 技术教程

原文地址：http://www.codeproject.com/Articles/142292/Recursive-methods-in-Csharp
作者：Shahin Khorshiadnia
译者：Tony Qu

Codeproject评分:

下载演示程序 – 20.7K

下载源代码 – 38.9K

什么是递归函数/方法？

任何一个方法既可以调用其他方法也可以调用自己，而当这个方法调用自己时，我们就叫它递归函数或递归方法。

通常递归有两个特点：

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);}3. 布尔组合

有时我们需要解决的问题比Fibonacci数列复杂很多，例如我们要枚举所有的布尔变量的组合。换句话说，如果n=3，那么我们必须输出如下结果：

true, true, truetrue, true, falsetrue, false, truetrue, false, falsefalse, true, truefalse, true, falsefalse, false, truefalse, 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），全部是用递归实现的。