what is the difference between re-entrant function and recursive function in C?

Answer 1

A function is re-entrant if it supports having multiple threads of execution "going through" it at the same time. This might be due to actual multi-threading, and I use this case below, or due to other things as pointed out by other posters. Multi-threading was the first that came to mind, and is perhaps also the easiest to understand, so I focused on that case.

This means that the function cannot use static "global" data, since that data would then be accessed by two (or more) threads in parallel, often breaking horribly. A re-entrant function often has an explicit argument to hold any call-specific state, rather than storing it statically.

strtok() is a classic case of a function in the C standard library that is well-known not to be re-entrant.

[Edit]: There are a bunch of insights, clarifications and corrections in the comments, so please read those as well! Thanks for the help, folks.

Answer 2

What unwind originally said is mostly correct - except that it is not limited to multi-threading (also, protecting global data with locks makes it thread safe - but not necessarily re-entrant). [Edit] He's fixed his post to account for this now :-)

A function may also be re-entered on the same thread as a result of recursion - either directly or indirectly (ie, function a calls function b which calls function c which calls function a).

Of course if you have protected against re-entrancy on the basis that multiple threads may call it then you are covered for the recursive cases too. That's not true the other way around, however.

Answer 3

It's easier to remember when you understand what the term means.

The term "re-entrant" means that it is safe to "re-enter" the function while it is already executed, typically in a concurrent environment.

In other words, when two tasks can execute the function at the same time without interfering with each other, then the function is re-entrant. A function is not re-entrant when the execution by one task has an impact on the influence of another task. This typically is the case when a global state or data is used. A function that uses only local variables and arguments is typically re-entrant.

Answer 4

"Re-entrance" of a function occurs when it is called before a previous invocation has returned. There are three main reasons for that to occur: recursion (the function calls itself), multi-threading and interruption. Recursion is normally easier, since it is clear that the function will be re-entered. Multi-threading and interruption are more tricky, as the re-entrance will be asynchronous. As stated in other answers, in most cases the function should not modify global data (reading global data is ok, some kings of writing is ok if protected as critical sections).

Answer 5

Here is it:

• A reentrant function can be called simultaneously by multiple threads provided that each invocation of the function references unique data.

• A thread-safe function can be called simultaneously by multiple threads when each invocation references shared data. All access to the shared data is serialized.

Shamelessly stolen from the Qt manual. But it's a short and concise definition. Basicially, a non-reentrant function is also not recursion-safe.

Now, what is a recursive function? It's a kind of definition of a function. Recursive function are defined in terms of themself. They reduce input, call theirself, until a basic case can be figured out without the need of calling theirself again.

So we have two things.

• recursive functions are a kind of definition.
• reentrant functions are functions that guarantee multiple threads can call them, provided each time unique data is accessed.

Now, the multiple-threads vehicle above serves only the purpose of having multiple activations of the function at the same time. But if you have a recursive function, you also have multiple activations of that functions at the same time. Most recursive functions therefor must be re-entrant too.