可重入和递归

Question

说每个递归函数都需要可重入是正确的说法吗？

Answer 1

如果可重入意味着对函数的进一步调用可能会在前一个函数结束之前开始，那么是的，所有递归函数都恰好是可重入的，因为从这个意义上来说，递归意味着可重入。

然而，“可重入”有时被用作“线程安全”的同义词，这引入了很多其他要求，从这个意义上来说，答案是否定的。在单线程递归中，我们有一种特殊情况，即一次只会执行一个函数“实例”，因为堆栈上的“空闲”实例都在等待其“子”实例返回。

Answer 2

不，我记得有一个与静态（全局）变量一起使用的阶乘函数。拥有静态（全局）变量不利于可重入，并且该函数仍然是递归的。

global i;

    factorial()
    { if i == 0 return 1;
      else { i = i -1; return i*factorial();

    }

这个函数是递归的并且是不可重入的。

Answer 3

“可重入”通常意味着两个不同的线程可以同时多次进入该函数。

为了可重入，它必须执行诸如保护/锁定对静态状态的访问之类的操作。

另一方面，递归函数不需要保护/锁定对静态的访问，因为它一次只执行一个语句。

所以：不。

Answer 4

一点也不。

例如，为什么递归函数不能拥有静态数据？它不应该能够锁定关键部分吗？

考虑一下：

sem_t mutex;
int calls = 0;

int fib(int n)
{
    down(mutex); // lock for critical section - not reentrant per def.
    calls++; // global varible - not reentrant per def.
    up(mutex);

    if (n==1 || n==0)
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

这并不是说编写递归和可重入函数很容易，也不是说它是常见模式，也不是说以任何方式推荐它。但这是可能的。