Sometimes in interviews, I may use recursion to solve a problem (such as adding 1 to an infinite precision integer), or when the problem presents itself suitable to use recursion. Sometimes, it might just be due to using recursion a lot for problem-solving, so without thinking much, recursion is used to solve the problem.
However, what are the considerations before you can decide it is suitable to use recursion to solve a problem?
Some thoughts I had:
If we use recursion on data which is halved every time, seems like it is no problem using recursion, as all the data that can fit into 16GB of RAM, or even an 8TB hard drive, can be handled by recursion just 42 level deep. (so no stack overflow (I think in some environment, the stack can be 4000 level deep, way more than 42, but at the same time, it also depends on how many local variables you have, as each call stack, occupy more memory if there are many local variables, and it is the memory size, not level, that determines stack overflow)).
If you calculate Fibonacci numbers using pure recursion, you really have to worry about the time complexity, unless you cache the intermediate results.
And how about adding 1 to an infinite precision integer? Maybe it is debatable, as, will you work with numbers that are 3000 digits long or 4000 digits long, so big that it can cause a stack overflow? I didn't think of it, but maybe the answer is no, we shouldn't use recursion, but just use a plain loop, because what if in some application, the number really need to be 4000 digits long, to check for some properties of the number, such as whether the number is prime or not.
The ultimate question is: what are the considerations before you can decide to use recursion to solve a problem?
Best Answer
One consideration is whether your algorithm is intended to be an abstract solution, or a practical executable solution. In the former case, the attributes you are looking for are correctness, and ease of understanding for your target audience1. In the latter case, performance is also an issue. These considerations may influence your choice.
A second consideration (for a practical solution) is whether the programming language (or more strictly, its implementation) that you are using do tail-call elimination? Without tail-call elimination, recursion is slower than iteration, and deep recursion may lead to stack overflow problems.
Note that a (correct) recursive solution can be transformed into an equivalent non-recursive solution, so you don't necessarily need to make a hard choice between the two approaches.
Finally, sometimes the choice between recursive and non-recursive formulations is motivated by the need to prove (in the formal sense) properties about an algorithm. Recursive formulations more directly allow proof-by-induction.
1 - This includes considerations like whether the target audience ... and this might include programmers reading practical code ... would view one style of solution as "more natural" than the other. The notion of "natural" will vary from person to person, depending on how they learned programming or algorithmics. (I challenge anyone who proposes "naturalness" as the primary criteria for deciding to use recursion (or not) to define "naturalness" in objective terms; i.e. how would you measure it.)