递归函数是可重入的吗

Question

我见过许多递归函数（主要用于计算一些数学运算，例如阶乘、数字中的数字之和等），其中涉及使用静态变量来保存每个递归调用/操作的结果，并且将其用于后续调用。

那么这是否会使递归函数变得不可出租且不是线程安全的。

递归函数是否还有其他不需要静态变量的用例？

Answer 1

递归函数还有其他不需要静态变量的用例吗？

当然。事实上，递归函数中的静态变量应该是例外，而不是规则：

我见过许多递归函数（主要用于计算一些数学运算，例如阶乘、数字中的数字之和等），其中涉及使用静态变量来保存每个递归调用的结果/操作，并将其用于后续调用。

坦率地说，这些都是非常糟糕的实现。这里绝对不需要静态变量。它们可能充当累加器；通过将累加器作为额外参数传递可以更好地完成此操作。

Answer 2

通过引用或更高的数据结构作为参数传递状态的递归函数是可重入的。

Answer 3

在我看来，你看到的例子是有缺陷的。编写递归函数的标准方法不使用或需要静态变量来存储结果；相反，您应该使用参数和/或返回值。使用静态确实会使它们变得不可出租，但它们不应该以这种方式编码。

使用返回值的示例 (JavaScript)：

function deepCollectChildText(node) {
    var text, child;

    text = "";
    for (child = node.firstChild; child; child = child.nextSibling) {
        switch (child.nodeType) {
            case 1: // element node, may contain child nodes
                text += deepCollectChildText(child);
                break;
            case 3: // text node
                text += child.value;
                break;
        }
    }
    return text;
}

不需要静态。它本可以使用一个进行编码，因此不可重入，但没有理由这样做。

Answer 4

递归函数是线程安全的，与普通函数一样，在我知道的所有语言体系结构中都支持递归。每个线程都有自己的堆栈，递归函数使用堆栈来存储变量和返回地址。

Answer 5

恕我直言，如果函数中使用静态或全局变量，它可能不是线程安全的。否则它是线程安全的。

Answer 6

回顾过去的实践，我从未考虑或实践过将静态变量用于递归函数。除了常量。

• 可重入函数不修改静态变量或共享资源，也不读取静态非常量或可修改的共享资源。
• 因此，可重入=>线程安全，但反之则不然。
• 修改静态变量的递归函数是不可重入的。

所以，
可重入递归函数是线程安全的。
然而，不可重入递归函数不是线程安全的，除非共享/静态资源的访问受到同步边界的有效约束。

那么下面的问题就需要回答了。
如果一个函数修改了数据库记录，是否会使其不再可重入？

我认为只要每次进入都实例化外部资源，该函数就是可重入的。例如，具有唯一身份运行密钥的数据库记录。每次进入都会生成带有新运行密钥的新记录。

然而，这实际上就像使静态变量线程安全一样吗？它认为它更像是一个线程安全的静态哈希表，为每个条目生成唯一的键、值对，因此条目之间不共享键、值对。

因此，当数据库记录或静态资源每次进入分配其资源的唯一实例时，函数实际上是可重入的，但我认为由于它依赖于外部共享资源的线程安全保护，学者可能会说它是线程-安全但不可重入。

对于这样的论点，我不敢苟同。例如，对于假设的编程语言，其规范不限制其任何实现使用共享数据库或全局散列来存储变量。因此，程序员不知道在该语言的实现下使用了线程安全管理的资源。因此，程序员继续编写一个“可重入”函数，或者他/她是这么认为的。那么这是否会使他/她的“可重入函数”不可重入？

因此，我的结论是，只要静态/共享资源每次进入分配一个唯一的实例，函数就是可重入的。

对于创造术语“entrantiation/re-entrantiation”表示歉意，因为我缺乏更好的词的知识。

Answer 7

两者是不同的概念。一个并不意味着另一个，反之亦然。

例如，这是一个递归函数（假设语言）吗？

global sum = 0

proc accumulate(treeNode)
    sum += treeNode.Value
    if treeNode.Left then accumulate(treeNode.Left)
    if treeNode.Right then accumulate(treeNode.Right)
end

显然它是一个递归函数，但由于使用了全局变量，所以它是不可重入的。这里的“全局”至少是指“对于函数来说不是本地的”。

然而，这是一个糟糕的例子，因为很容易通过简单地返回总和来使其完全不依赖全局变量：

func accumulate(treeNode)
    sum = treeNode.Value
    if treeNode.Left then sum += accumulate(treeNode.Left)
    if treeNode.Right then sum += accumulate(treeNode.Right)
    return sum
end

递归函数的概念中没有任何固有的东西使其成为非线程安全或可重入的，或者相反，这完全取决于您在相关函数中实际编写的内容。