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

本文关键字：什么 递归 | 更新日期: 2023-09-27 17:56:10

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

我目前对递归的理解是，它是方法调用自己的任何时候。

即 

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

是的，它仍然是递归。有不同类型的递归，如尾递归、树递归等。你可以看看谷歌休息。

顺便说一下，在第二种情况下，如果 i 的值大于或等于 2，您将收到堆栈溢出错误，因为每个堆栈都会调用另一个。

相关文章：