Question

Difference between recursive and reentrant functions

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.