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?
1to infinite precision integer? You can say, yes, they reduce to a smaller problems, but pure recursion is not suitable for it