3

我正在学习数据结构和算法。我发现理解递归特别困难。所以我有以下问题。但它们与任何特定代码无关。

  1. 当我实现方法时，我应该何时/何处考虑递归？
  2. 在一般编码约定中，如果它们都可行，我应该更喜欢递归而不是简单迭代吗？
  3. 如何真正理解大多数可能的递归形式，以便我可以在需要时想到它们？学习它的最佳方法是什么？（任何相关的书籍或网站？）有什么模式吗？

我知道如果您发现递归简单自然，这个问题可能听起来不具建设性。但对我来说，这与我的直觉不太相符。我很感激任何帮助。

4

4 回答 4

4

1

当数据可以被视为相似时，问题的递归解决方案通常会更小。例如。如果你有一棵二叉树并且你想得到你定义sum-tree为的所有叶节点的总和如果它是一个叶节点，它的总和就是它的值，如果它不是一个叶节点，它是两个子树的总和.

这是我的文本的方案实现

(define (sum-tree tree)
  (if (leaf? tree)
      (node-value tree)
      (+ (sum-tree (node-left tree))
         (sum-tree (node-right tree)))))

或者在 Java 中也一样，定义为 Node 类中的方法。

public int sum()
{
    if ( isLeaf() )
        return value;
    else
        return left.sum() + right.sum();
}

对此的迭代解决方案将更长且更难阅读。在这种情况下，您应该更喜欢递归。

2

这取决于。如果您使用 Python 或 Java 编程，则不应该这样做，因为它们没有尾递归。然而，对于 Scheme，这是唯一的出路。如果您的语言支持尾递归，您应该在代码更清晰时选择递归。

3

通过实践学习。您需要编写一些使用递归作为工具的算法。如果您不确定纸叠的流向，请使用纸张跟随纸叠的流向。学习一些 Scheme 或类似的函数式语言可能会对您有很大帮助。

于 2013-09-23T13:45:06.933 回答
1
  1. 当您一遍又一遍地重复相同的事情时，可以使用递归。例如，你正在遍历一棵树，你可以使用递归的方法去到左边或右边的孩子。
  2. 我会选择更容易阅读的那个。一般来说，简单迭代会更快，因为它没有任何开销（递归有一些开销，如果级别太深会导致堆栈溢出，而简单迭代不会）。但在某些情况下，编写递归函数比在简单迭代中编写等效函数要容易得多。
  3. 我宁愿先看问题，然后再决定是否需要递归来解决，反之亦然。任何算法书都应该足够好。也许您可以重新阅读http://en.wikipedia.org/wiki/Recursion开始。那里有一个关于递归的简单示例，我认为您也可以使用简单的迭代来实现。
于 2013-09-23T01:55:21.210 回答
1

起初，我也很难理解递归。当我学习递归时，它是在上学时使用Java. 我发现我经常会在迭代器上使用递归，因为用 Java 编写它们很烦人。然而，我学会了Ruby，我发现自己编写递归方法的次数越来越少。然后，我学习Elixir并Erlang发现自己编写了很多递归函数。我的观点？有些工具会给自己以某种风格进行写作。

现在回答您的问题，因为您才刚刚开始学习递归，我建议您深入研究它们并尽可能多地编写它们以适应它们。

使用递归（例如斐波那契数列、遍历树等）可以更好地完成某些任务。其他一些你最好写一个简单的循环。但是，请注意，您可以编写任何带有循环的递归方法。不过，在某些情况下它可能会变得棘手。

总而言之，一旦你掌握了递归，它实际上是一个非常酷的概念。

看看这个与递归有关的问题：Erlang 练习，创建列表

于 2013-09-23T01:59:10.120 回答
1

我会去研究一些众所周知的递归算法。例如，您可以尝试实现阶乘计算，或获取树中的所有路径长度。

通过这样做，您将（希望）了解递归方法如何帮助简化代码，以及为什么在这些特定情况下它是一种好方法。这可以为您未来的应用提供一些想法:)

于 2013-09-23T13:51:24.747 回答