What are the considerations to determine whether you can use recursion to solve a problem?

Question

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?

Answer 1

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 audience¹. 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.)}

Answer 2

As a C/C++ programmer, my top consideration is performance. My decision process is something like:

1. What is the maximal depth of the call stack? If too deep, get rid of the recursion. If shallow, go to 2.

2. Is this function likely to be a bottleneck of my program? If yes, go to 3. If no, keep the recursion. If unsure, run a profiler.

3. What is the fraction of CPU time spent on recursive function calls? If function calls take significantly less time than the rest of the function body, it is ok to use recursion.

Answer 3

However, what are the considerations before you can decide it is suitable to use recursion to solve a problem?

When writing functions in Scheme, I find it natural to write tail recursive functions without thinking too much.

When writing functions in C++, I find myself debating before I use a recursive function. The questions that I ask myself are:

• Can the computation be performed using an iterative algorithm? If yes, use an iterative approach.

• Can the depth of recursion grow by the size of the model? I recently ran into a case where the depth of recursion grew to almost 13000 due to the size of the model. I had to convert the function to use an iterative algorithm post-haste.

  For this reason, I wouldn't recommend writing a tree traversal algorithm using recursive functions. You never know when the tree becomes too deep for your run time environment.

• Can the function become too convoluted by using an iterative algorithm? If yes, use a recursive function. I haven't tried writing qsort using an iterative approach but I have a feeling using a recursive function is more natural for it.

Answer 4

For Fibonacci numbers, the naive "recursion" is just totally stupid. That's because it leads to the same subproblem being solved over and over again.

There is actually a trivial variation of the Fibonacci numbers where recursion is very efficient: Given a number n ≥ 1, calculate both fib (n) and fib (n-1). So you need a function that returns two results, lets call this function fib2.

The implementation is quite simple:

function fib2 (n) -> (fibn, fibnm1) {
    if n ≤ 1 { return (1, 1) }
    let (fibn, fibnm1) = fib2 (n-1)
    return (fibn + fibnm1, fibn)
}