2022年c递归函数详细介绍及使用方法 .pdf
精品资料欢迎下载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 页，共 11 页 - - - - - - - - - 精品资料欢迎下载调用栈图示下面我打算介绍一些例子来帮助你更好的理解递归的风险和回报。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-) 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 精品资料欢迎下载 value *= i; return value; 下面是用递归的方法实现计算阶乘，与之前的代码比起来它更简洁。. 代码如下 : public long Factorial(int n) if (n = 0)/ 限制条件，对该方法调用自己做了限制return 1; return n * Factorial(n - 1); 你知道的， n 的阶乘实际上是n-1 的阶乘乘以n，且 n0。它可以表示成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 = 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 精品资料欢迎下载Fn-1 + Fn-2 下面的方法就是用来计算Fn 的（没有递归，性能好）. 代码如下 : public long Fib(int n) if (n 2) return n; long f = new longn+1; f0 = 0; f1 = 1; for (int i = 2; i = n; i+) fi = fi - 1 + fi - 2; return fn; 如果我们使用递归方法，这个代码将更加简单，但性能很差。. 代码如下 : 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 精品资料欢迎下载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, 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) 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 精品资料欢迎下载 if (counter = 0) return; bool booleans = new bool2 true, false ; for (int j = 0; j 2; j+) StringBuilder stringBuilder = new StringBuilder(result); stringBuilder.Append(string.Format(0 , booleansj.ToString().ToString(); if (counter = 1) Console.WriteLine(stringBuilder.ToString(); CompositionBooleans(stringBuilder.ToString(), counter - 1); 现在让我们来调用上面这个方法：. 代码如下 : CompositionBoolean(string.Empty, 3); Ian Shlasko建议我们这样使用递归：. 代码如下 : 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 精品资料欢迎下载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) 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 精品资料欢迎下载 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 。例如：. 代码如下 : 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 精品资料欢迎下载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 errors = new Dictionary(); private List result = new List(); private void SearchForFiles(string path) 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 精品资料欢迎下载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 这个方法似乎不需要满足任何条件，因为每个目录如果没有子目录，会自动遍历所有子文件。总结名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 精品资料欢迎下载我们其实可以用递推算法来替代递归，且性能会更好些，但我们可能需要更多的时间开销和非递归函数。但关键是我们必须根据场景选择最佳实现方式。James MaCaffrey 博士认为尽量不要使用递归，除非实在没有办法。你可以读一下他的文章。我认为：A) 如果性能是非常重要的，请避免使用递归B)如果递推方式不是很复杂的，请避免使用递归C) 如果 A 和 B 都不满足，请不要犹豫，用递归吧。例如：第一节（阶乘） ：这里用递推并不复杂，那么就避免用递归。第二节（ Fibonacci） ：像这样的递归并不被推荐。当然，我并不是要贬低递归的价值，我记得人工智能中的重要一章有个极小化极大算法（Minimax algorithm ） ，全部是用递归实现的。但是如果你决定使用队规方法，你最好尝试用存储来优化它。版权声明：本文由作者Tony Qu 原创，未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则视为侵权。名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页，共 11 页 - - - - - - - - -
