递归函数是否可重入

Question

我已经看到很多递归函数(主要用于计算一些数学运算,例如阶乘,数字中的数字之和等等),这些函数涉及使用保存每个递归调用/操作结果的静态变量,以及将它用于后续调用.

那么这会使递归函数非租用而不是线程安全的.

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

Answer 1

这两个是不同的概念.一个并不意味着另一个,反之亦然.

例如,这是一个递归函数(假设语言)吗？

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

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

Answer 2

是否存在其他不需要静态变量的递归函数用例.

当然.实际上,递归函数中的静态变量应该是例外,而不是规则:

我已经看到很多递归函数(主要用于计算一些数学运算,例如阶乘,数字中的数字之和等等),这些函数涉及使用保存每个递归调用/操作结果的静态变量,以及将它用于后续调用.

这些都是非常坦率的糟糕实施.这里绝对不需要静态变量.他们可能充当蓄电池; 这可以通过将累加器作为额外参数传递来更好地完成.