2

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

这是否使递归函数不可租用且不是线程安全的。

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

4

7 回答 7

11

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

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

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

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

于 2010-01-31T11:36:59.003 回答
5

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

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

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

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

于 2010-01-31T11:39:11.750 回答
1

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

于 2010-01-31T11:36:42.330 回答
1

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

使用返回值 (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;
}

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

于 2010-01-31T11:37:01.190 回答
0

回顾过去的做法，我从未考虑或实践过使用静态变量来实现递归函数。常量除外。

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

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

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

我在想，只要每次进入都实例化外部资源，该功能就是可重入的。例如，具有唯一标识运行键的数据库记录。每次进入都会生成具有新运行密钥的新记录。

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

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

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

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

为创造术语进入/重新进入而道歉，因为我缺乏更好的词的知识。

于 2010-01-31T12:56:07.990 回答
0

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

于 2010-01-31T11:36:24.160 回答
0

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

于 2010-01-31T11:40:41.127 回答