11

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?

  • 7
    It's actually rather simple: "Is the solution trivial if I can assume that the solution to a slightly smaller problem is known?" – Kilian Foth Apr 24 '17 at 10:27
  • but what about Fibonacci number or adding 1 to infinite precision integer? You can say, yes, they reduce to a smaller problems, but pure recursion is not suitable for it – 太極者無極而生 Apr 24 '17 at 11:42
  • You may find this helpful - stackoverflow.com/questions/3021/… – Kishor Kundan Apr 25 '17 at 4:30
16

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.)

  • 2
    Some problems are simply more naturally expressed using recursion. Tree traversal, for example. – Frank Hileman Apr 24 '17 at 21:06
  • Updated my answer to address that point, – Stephen C Apr 25 '17 at 1:16
  • 1
    With regards to "naturalness": tree traversal without recursion, for example, tends to produce larger, less general purpose code. Consider for example using polymorphic calls to traverse the tree, with different behavior for leaf and composite nodes. This is not possible without recursion. – Frank Hileman Apr 25 '17 at 13:41
  • 1) Did you take up my challenge to define "natural" yet? 2) Since it is possible to simulate recursion using a stack data-structure, it is possible to implement tree traversal that way too. It may not be the most efficient way ... and it won't give you the most readable code ... but it is definitely possible, and practical to do it. – Stephen C Apr 25 '17 at 14:12
  • By the way, the first programming language that I learned (FORTRAN 4) did not support recursion at all. – Stephen C Apr 25 '17 at 14:15
1

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.

1

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.

0

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)
}
  • do you think you can write the program in a common language? and your fib2 returns a pair of numbers, and your fib2() doesn't fit the interface of fib(), which is, given a number, return a number. It seems your fib(n) is to return fib2(n)[0] but please be specific – 太極者無極而生 Aug 5 '17 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.