Reentrancy and recursion

Would it be a true statement to say that every recur开发者_如何学Csive function needs to be reentrant?

If by reentrant you mean that a further call to the function may begin before a previous one has ended, then yes, all recursive functions happen to be reentrant, because recursion implies reentrance in that sense.

However, "reentrant" is sometimes used as a synonym for "thread safe", which is introduces a lot of other requirements, and in that sense, the answer is no. In single-threaded recursion, we have the special case that only one "instance" of the function will be executing at a time, because the "idle" instances on the stack are each waiting for their "child" instance to return.

No, I recall a factorial function that works with static (global) variables. Having static (global) variables goes against being reentrant, and still the function is recursive.

global i;

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

    }

This function is recursive and it's non-reentrant.

'Reentrant' normally means that the function can be entered more than once, simultaneously, by two different threads.

To be reentrant, it has to do things like protect/lock access to static state.

A recursive function (on the other hand) doesn't need to protect/lock access to static state, because it's only executing one statement at a time.

So: no.

Not at all.

Why shouldn't a recursive function be able to have static data, for example? Should it not be able to lock on critical sections?

Consider:

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

This does not go to say that writing a recursive and reentrant function is easy, neither that it is a common pattern, nor that it is recommended in any way. But it is possible.