Recursion is fun. However, in safety-critical application it is regarded as a dangerous thing (because of stack overflow I suppose?).
Imagine you need to deal with a your favorite language's subset, that would not allow recursion - would that a disaster for you?
Formal question: for every recursive function there could be created a totally equivalent non-recursive one - is that true? is there a theorem about it or something?
Think about it like this: your program is executed by a finite set of CPUs (let's assume you have 1 at the moment), executing a sequence of instructions. How does the CPU handle recursion? It cannot create a new instance of itself solving a slightly simpler problem, so it uses a stack to keep track of where it is. So, for any algorithm you can express recursively in any programming language, you can also manually "unroll" the recursion the same way the CPU does, using a stack. (Note that for many algorithms, particularly ones with only one recursive call, there are usually simpler ways to remove the recursion, such as simple iteration.)
Yes every such function can be rewritten as a non-recursive one. I'm not sure there's a formal way to do it, but it is referred to as "recursion unrolling" or "recursion unfolding" in literature.
In most situations, recursion is to be avoided. Especially in the mentioned kind of systems, MISRA-C bans recursion for example.
There are a few rare situations where recursion is handy and makes the code more efficient, some binary tree implementations etc.
But the main purpose of recursion is to teach it to confused students, so that when they become experienced, they can teach it to confused students, so that-... :)
Usually recursion is used because there is no easy way to know how many times you'll need to iterate over a problem.
Replacing a recursive function with simple looping may require a lot of extra work, but should usually be possible if you feel it necessary.
There's little danger of stack overflow if your recursive function has a proper base case, though.
Recursion is not free
It takes a considerable amount of memory space (usually on the stack)
And CPU time (by using calls, rebuilding stack frames etc).
In tight loops this makes a recursive algorithm slower than its non-recursive equivalent.
If speed and stack limits are not an issue, by all means leave the recursion in, but if you use recursion in a tight loop, (which is often the case)
You gain a lot of optimization options by straitening out the recursion.
Because: maybe:
1. You don't need to save all those registers/variables
2. You don't have to jump back to the exact same place where you come from.
3. You don't need to call that cleanup code for every recursion
4. You can unroll some loops
5. You can use an inline directive on that non-recursive routine.
My mean issue with recursion is the datastructure it most often is used on: trees.
Trees require pointers and pointers require random memory access (they jump all over the place) this is bad for cache usage because sequential access is much faster than random access.
If you replace a binary tree with an 2D array you will waste 50% of the space, (unless you stack another tree upside down in the array), but you gain sequential access options for many of the leaves and you don't have to use pointers, saving space.
Example of a binary tree stored in an array
+-----------------+
|0eeeeeeeeeeeeeeee| //no pointers needed, parent/child, is y dimension,
|11 dddddddd| //sibbling is x dimension of the array.
|2222 cccc| //The 123 tree is stored root up.
|33333333 bb| //Notice how the abc-tree is stored upside down
|4444444444444444a| //The wasted space in the middle, is offset by the fact
+-----------------+ //that you do not need up, down, and sibbling pointers.
