递归的相关性

Question

所以我目前正在尝试掌握递归的概念，并且我理解我遇到的大部分问题，但我觉得它的使用不适用于太多的计算问题。但这只是新手的假设，所以我想问，作为程序员，递归有很多实际用途吗？另外，它可以解决哪些典型问题？我见过的唯一的问题是堆排序和脑筋急转弯类型的问题，例如“河内塔”，它看起来非常具体且缺乏广泛的用途。

谢谢

Answer 1

递归在编程中有很多用途 - 一个典型的例子是导航树结构，您可以在发现的每个子元素的情况下调用导航函数等。

Answer 2

以下是一些如果没有递归几乎不可能实现的领域：

• XML、HTML 或任何其他树状文档结构
• 编译和解析
• 自然语言处理
• 分而治之算法
• 许多数学概念，例如阶乘

递归可以为原本复杂的问题带来极其优雅的解决方案。如果您对编程作为一门艺术感兴趣，那么您确实应该更深入地研究。

哦，如果您不确定，这是递归的可靠定义：

递归（名词）：参见“递归”

Answer 3

我想这取决于你要做什么。作为从事企业 Web 工作的 C#/ASP.NET 开发人员，我每年编写的递归函数可能还不到一个。当我摆弄我的爱好代码（主要是统计研究）时，我发现有更多应用递归的机会。部分原因是主题，部分原因是我更依赖客户在进行公司工作时已经决定的第三方库（其中实现了需要递归的算法）。

Answer 4

它不是你每天都使用的东西。但许多有关数据搜索和排序的算法都可以利用它。一般来说，大多数递归算法也可以使用迭代来编写；通常，递归版本更简单。

Answer 5

如果您检查与此问题“相关”列出的问题，您会发现有关递归的“过多”内容，这将帮助您更好地理解它。

递归并不是什么新鲜事，也不仅仅是一个玩具概念。递归算法早在计算机出现之前就已经存在了。

“阶乘”的经典定义就是一个很好的例子：

fact(x) =
if x < 0 then fact(x) is undefined
if x = 0 then fact(0) = 1
if x > 0 then fact(x) = x * fact(x-1)

这不是由认为递归是一个很酷的玩具的计算机极客创建的。这是标准的数学定义。

Answer 6

调用递归作为一种程序构造，几乎不应该使用，除非在非常高级的语言中，您希望编译器将其优化为不同的构造。使用调用递归，除非您可以在深度上建立较小的界限，否则会导致堆栈溢出，而不是为您解答问题的良好堆栈溢出。 :-)

另一方面，递归作为一个算法概念非常有用。它对于处理任何递归定义的数据格式（例如 HTML 或 XML，或分层文件系统）以及在搜索、排序和（每个人最喜欢的）图形渲染等无数其他领域中实现重要算法至关重要。

Answer 7

有几种语言不支持循环（即 for 和 while），因此当您需要重复行为时，您需要使用递归（我相信 J 没有循环）。在许多示例中，递归需要少少的代码。比如我写了一个isPrime方法，只用了两行代码。

public static boolean isPrime(int n)
{
返回 n!=1&&isPrime(n,2);
}

public static boolean isPrime(int n,int c)
{
返回c==n||n%c!=0&&isPrime(n,c+1);
另一个

迭代解决方案将需要更多代码：

public static boolean isPrime(int n)
{
    if(n==1) return false;
    int c=2;
    while(c!=n)
    {
        if(n%c==0) return false;
    }
    return true;
}

很好的例子是当您使用 ListNodes 时，例如，如果您想检查 ListNode 中的所有元素是否相同，则递归解决方案会花费更多更轻松。

public static <E> boolean allSame(ListNode<E> list)
    {
        return list.getNext()==null||list.getValue().equals(list.getNext().getValue())&&allSame(list.getNext());
    }

迭代解决方案看起来像这样：

public static <E> boolean allSame(ListNode<E> list)
{
    while(list.getNext()!=null)
    {
        if(!list.getValue().equals(list)) return false;
        list=list.getNext();
    }
    return true;
}

正如您所看到的，在大多数情况下，递归解决方案比迭代解决方案更短。