Reentrancy and recursion

Question

Would it be a true statement to say that every recursive function needs to be reentrant?

Answer 1

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.

Answer 2

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.

Answer 3

'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.

Answer 4

Not exactly. Reentrant function needs to be able to handle concurrent execution with different threads.

Recursive function must be able to handle entry while it is still running but access is done in controlled manner and not by other threads.

Answer 5

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.