65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 C# 进行递归方法

Shahin Khorshidnia
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.44/5 (68投票s)

2011年1月4日

CPOL

4分钟阅读

viewsIcon

933629

downloadIcon

2896

面向初学者，递归简介、示例、优点和缺点。数据结构的一部分。

什么是递归函数/方法？

一个方法可以调用其他方法，但它也可以调用自身。当一个方法调用自身时，它就被称为递归方法。
递归通常有两个规范

  1. 递归方法会调用自身多次，直到满足条件。
  2. 递归方法有参数，并使用新的参数值调用自身。

那么，什么是递归函数？函数和方法之间没有区别，除了函数不能在其类外部使用。在 C# 中，我们只有方法，但自 .NET Framework 3.5 起，匿名函数已添加到 C# 中。（更多信息）

因此，最好说递归方法而不是递归函数，并且我在本文中都用递归。

为什么、何时以及如何在我们的应用程序中使用递归？

“任何可以使用赋值、if-then-else语句和while语句编写的程序，也可以使用赋值、if-then-else和递归来编写。”（《C 语言数据结构基础》作者：Ellis Horowitz）

递归解决方案是一种强大而简单的方法，适用于复杂的开发，但它可能会因为反复使用调用堆栈而导致性能下降（有时甚至会造成性能问题）。

请看图示

调用堆栈图

我将举例说明其风险和收益，以便更好地理解。

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)//The condition that limites the method for calling itself
        return 1;
    return n * Factorial(n - 1);
}

您知道，n 的阶乘实际上是 (n-1) 的阶乘乘以 n，如果 n > 0。

或者:

Factorial(n) 返回 Factorial(n-1) * n

这就是方法的返回值；在此之前，我们需要一个条件。

如果 n = 0 则返回 1

我认为，程序逻辑现在已经很清楚了，我们可以理解它。

2. 斐波那契数列

斐波那契数列是以下数列中的数字：

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)//satisfaction condition
        return n;
    return Fib(k - 2) + Fib(k - 1);
}

3. 布尔组合

有时解决问题比斐波那契数列更复杂。例如，我们想显示 n 个布尔变量的所有可能组合。换句话说，如果 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. InnerExceptions (内部异常)

递归方法对于获取最后一个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)//Condition for limiting
    return ex;
return GetInnerException(ex.InnerException);//Calling the method with inner exception parameter

现在，当出现异常时，我们可以找到该异常的最后一个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 McCaffrey 博士认为，除非必要，否则不要使用递归。阅读他的文章。

我宁愿：:
A) 当性能是极其非常重要的关键主题时，避免使用递归。
B) 当迭代不是很“复杂”时，避免使用递归。
C) 如果 (!A && !B)，则不要犹豫使用递归。

例如

第一部分（阶乘）：迭代并不复杂，因此避免递归。

第二部分（斐波那契）：不推荐像这样使用递归。

当然，这并不降低递归的价值；我可以提醒您极小极大算法（人工智能中的一个重要章节），递归是其全部。

但是，如果您决定使用递归方法，最好尝试使用记忆化对其进行优化。

祝您好运！

© . All rights reserved.