c# - 什么是递归，什么不是递归？

Question

我试图理解到底什么是递归，但无法找到以下问题的答案。

我目前对递归的理解是，只要方法调用自身，就可以递归。

IE

Menu() 
{
if(i<2)
{Console.WriteLine();}
else
{Menu();}    
}

上面是一个方法调用自身的递归示例。

我不确定的是这样的场景:

Menu() 
{
if(i<2)
{Console.WriteLine();}
else
{Console.WriteLine("Something Went Wrong!"); MenuError();}    
}

MenuError() 
{
Console.WriteLine("Something went wrong!");
Menu();
}

如果该方法调用一个方法，然后该方法又调用它，这仍然是递归吗？

Answer 1

My current understanding of recursion is that it is anytime a method calls itself.

这是正确的。递归定义是自引用定义。

递归定义的两个有趣的属性是生产力和终止。如果一个程序继续产生输出，那么它就是高效的，尽管完整的输出可能永远不会出现(因此它可能不会终止)。如果程序在有限时间内产生完整输出，则程序终止。

例如，这是一个高效的、非终止的程序:

Naturals(int i) {
  Console.WriteLine(i);
  Naturals(i + 1);
}

这是一个正在终止的程序:

UpToTen(int i) {
  Console.WriteLine(i);
  if (i < 10) UpToTen(i + 1);
}

这是一个非生产性程序:

DoNothing() {
  DoNothing();
}

---

如果Menu来电 MenuError ，和MenuError来电 Menu ，这有时称为相互递归。唯一的区别是我们的组织；我们可以通过内联 MenuError 重写代码，使其只有一个方法.

Menu()  {
  if (i < 2) {
    Console.WriteLine();
  }
  else {
    Console.WriteLine("Something Went Wrong!");
    Console.WriteLine("Something went wrong!");
    Menu();
  }
}

您实际上可以抽象递归本身:

// General definition
A Fix<A>(Func<Func<A>,A> f) {
  return f(() => Fix(f));
}

// Special definition for void functions
void Fix(Action<Action> f) {
  f(() => Fix(f));
}

void Menu(Action menu) {
  if (i < 2) {
    Console.WriteLine();
  }
  else {
    Console.WriteLine("Something Went Wrong!");
    Console.WriteLine("Something went wrong!");
    menu();
  }
}

Fix(Menu);

这是另一个使用 Fix 的示例定义阶乘函数。

Func<int, int> Fac(Func<Func<int, int>> fac) {
  return i => i == 0 ? 1 : i * fac()(i - 1);
}

// Fix<Func<int, int>>(Fac)  is the factorial function

您可能想知道为什么Fix没有签名A Fix<A>(Func<A,A> f)反而。这是因为 C# 是一种严格的语言，这意味着它在计算函数应用程序之前先计算参数。使用更简单的签名，C# 程序最终会陷入无限递归。