Reentrancy and recursion

Question

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

Answer 1

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.

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.