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

https://stackoverflow.com/questions/9038739

20-04-2021
|

Question

In C I know about the recursive function but I heard about the re-entrant function.

What is that? And whats the difference between them?

Solution

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.

OTHER TIPS

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.

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.

"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).

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.

A Re entrant function is a function which guaranteed that which can be work well under multi threaded environment. mean while function is access by one thread, another thread can call it... mean there is separate execution stack and handling for each... So function should not contain any static or shared variable which can harm or disturb the execution..

Mean function which can be called by thread, while running from another thread safely...... and properly.... hope I have answered the correct thing....

And of course rem that re-entrant function is not same as recursive function.... totally different concept.... A Re entrant function is a function which guaranteed that which can be work well under multi threaded environment. mean while function is access by one thread, another thread can call it... mean there is separate execution stack and handling for each... So function should not contain any static or shared variable which can harm or disturb the execution..

mean it should not contain any static or shared variable....

Mean function which can be called by thread, while running from another thread safely...... and properly.... hope I have answered the correct thing....

And of course rem that re-entrant function is not same as recursive function.... totally different concept....

All re-entrant code is a recursion but not all recursion is a re-entrant. Example for recursion is, any function, which calls itself directly or indirectly. Example for re-entant is, interrupt handler routines.

All recursive code are re-entrant...but not all re-entrant code recursive.

Licensed under: CC-BY-SA with attribution

Not affiliated with StackOverflow