It is well known that every recursive function can be implemented in an iterative version.
However, recursive functions, in general, have some overhead regarding the management of the stack.
Considering this, I would like to know if there are general principles that allow us to decide when the recursive version is better than the iterative version of a given function, supposing that both have the same time complexity.
While a recursive function might have some additional overhead versus a loop calling the same function, other than this the differences between the two approaches is relatively minor.
The major driving factor for choosing recursion over an iterative approach is the complexity (i.e. running time) of the problem being solved. The canonical example of where iteration massively beats out recursion is the Fibonacci sequence.
Computing the fifth Fibonacci number using recursion requires computing:
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(3) = f(2) + f(1)
The above takes four recursive calls and roughly 10 function evaluations. On the other hand, if we instead used dynamic programming and built up Fibonacci iteratively, we would only need two function calls (both f(1) and f(2) are constant values of 1):
f(3) = f(2) + f(1) (first call)
f(4) = f(3) + f(2) (second call)
The advantage of using an iterative becomes more apparent when computing larger values of the Fibonacci sequence, e.g. f(100), where recursion explodes via stack overflow.
