recursion - 重入和递归

Question

说每个递归函数都需要是可重入的，这是否正确？

Answer 1

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

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

Answer 2

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

global i;

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

    }

这个函数是递归的，它是不可重入的。

Answer 3

一点也不。

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

考虑：

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);
}

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

Answer 4

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

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

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

所以不行。