recursion - 递归函数难以理解

Question

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

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

我知道如果您发现递归简单而自然，这个问题可能听起来没有建设性。但对我来说，它不太符合我的直觉。我非常感谢任何帮助。

Answer 1

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或类似的函数式语言可能会对你有很大帮助。