views:

77

answers:

5

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

A: 

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.

Yuval A
Why shouldn't a reentrant function have static data?
Daniel Earwicker
Daniel: It's against the definition: http://en.wikipedia.org/wiki/Reentrant_%28subroutine%29 unless, you have a different one.
Noon Silk
That page is ridiculous (check the discussion page). Consider the APIs for accessing a file system - they access shared global data and yet can be called simultaneously from multiple threads/processes.
Daniel Earwicker
Adding a mutex doesn't make that reentrable: one thread will return the wrong result, if another thread is still using/inside the function.
ChrisW
If a file system is thread-safe because it uses locks to protect static data, then that's because those of its subroutines which access static data aren't themselves reentrable (which is why they need the protection).
ChrisW
A: 

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.

pakore
+1  A: 

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

ChrisW
A: 

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.

Josip Medved
+1  A: 

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.

Daniel Earwicker