什么是递归？

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

我目前对递归的理解是它是一个方法自己调用的.

那是正确的.递归定义是自引用定义.

递归定义的两个有趣属性是生产率和终止.如果程序继续产生输出,则程序是有效的,尽管完整输出可能永远不会到来(因此它可能不会终止).如果程序在有限时间内产生完整输出,则程序终止.

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

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#程序最终将进行无限递归.