什么是递归，什么不是递归？

debugcn 发表于 Dev

假脱机程序

我试图了解什么是递归，却无法找到以下答案。

我目前对递归的理解是，它可以在任何时候调用方法本身。

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();
}

如果该方法调用了某个方法，然后又调用了该方法，这是否仍然是递归？

埃里斯科

我目前对递归的理解是，它可以在任何时候调用方法本身。

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

递归定义的两个有趣的属性是生产力和终止。如果一个程序继续产生输出，则它是有生产力的，尽管完整的输出可能永远不会出现（因此它可能不会终止）。如果程序在有限时间内产生了全部输出，则该程序将终止。

例如，这是一个富有成效的，非终止性的程序：

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＃程序将以无限递归结束。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。

编辑于2021-06-25

我来说两句

0条评论

登录后参与评论

来自分类Dev