Recursion vs While Loops – Code Quality Comparison

code-qualityrecursion

I was reading about some development interview practices, specifically about the technical questions and tests asked at interviews and I've stumbled quite a few times over sayings of the genre "Ok you solved the problem with a while loop, now can you do it with recursion", or "everyone can solve this with a 100 lines while loop, but can they do it in a 5 lines recursive function?" etc.

My question is, is recursion generally better than if/while/for constructs?

I've honestly always thought that recursion is not to be preferred, because it's limited to the stack memory which is a lot smaller than the heap, also doing a great number of function/method calls is suboptimal from a performance standpoint, but I may be wrong…

Best Answer

Recursion is not intrinsically better or worse than loops - each has advantages and disadvantages, and those even depend on the programming language (and implementation).

Technically, iterative loops fit typical computer systems better at the hardware level: at the machine code level, a loop is just a test and a conditional jump, whereas recursion (implemented naively) involves pushing a stack frame, jumping, returning, and popping back from the stack. OTOH, many cases of recursion (especially those that are trivially equivalent to iterative loops) can be written so that the stack push / pop can be avoided; this is possible when the recursive function call is the last thing that happens in the function body before returning, and it's commonly known as a tail call optimization (or tail recursion optimization). A properly tail-call-optimized recursive function is mostly equivalent to an iterative loop at the machine code level.

Another consideration is that iterative loops require destructive state updates, which makes them incompatible with pure (side-effect free) language semantics. This is the reason why pure languages like Haskell do not have loop constructs at all, and many other functional-programming languages either lack them completely or avoid them as much as possible.

The reason why these questions appear so much in interviews, though, is because in order to answer them, you need a thorough understanding of many vital programming concepts - variables, function calls, scope, and of course loops and recursion -, and you have to bring the mental flexibility to the table that allows you to approach a problem from two radically different angles, and move between different manifestations of the same concept.

Experience and research suggest that there is a line between people who have the ability to understand variables, pointers, and recursion, and those who don't. Almost everything else in programming, including frameworks, APIs, programming languages and their edge cases, can be acquired through studying and experience, but if you are unable to develop an intuition for these three core concepts, you are unfit to be a programmer. Translating a simple iterative loop into a recursive version is about the quickest possible way of filtering out the non-programmers - even a rather inexperienced programmer can usually do it in 15 minutes, and it's a very language-agnostic problem, so the candidate can pick a language of their choice instead of stumbling over idiosyncracies.

If you get a question like this in an interview, that's a good sign: it means the prospective employer is looking for people who can program, not people who have memorized a programming tool's manual.

Related Solutions

Algorithms – How to Convert Loop to Recursion or Vice Versa

Actually you should break the function down first:

A loop has a few parts:

the header, and processing before the loop. May declare some new variables
the condition, when to stop the loop.
the actual loop body. It changes some of the header's variables and/or the parameters passed in.
the tail; what happens after the loop and return result.

Or to write it out:

foo_iterative(params){
    header
    while(condition){
        loop_body
    }
    return tail
}

Using these blocks to make a recursive call is pretty straightforward:

foo_recursive(params){
    header
    return foo_recursion(params, header_vars)
}

foo_recursion(params, header_vars){
    if(!condition){
        return tail
    }

    loop_body
    return foo_recursion(params, modified_header_vars)
}

Et voilà; a tail recursive version of any loop. breaks and continues in the loop body will still have to be replaced with return tail and return foo_recursion(params, modified_header_vars) as needed but that is simple enough.

Going the other way is more complicated; in part because there can be multiple recursive calls. This means that each time we pop a stack frame there can be multiple places where we need to continue. Also there may be variables that we need to save across the recursive call and the original parameters of the call.

We can use a switch to work around that:

bar_recurse(params){
    if(baseCase){
        finalize
        return
    }
    body1
    bar_recurse(mod_params)
    body2
    bar_recurse(mod_params)
    body3
}


bar_iterative(params){
    stack.push({init, params})

    while(!stack.empty){
        stackFrame = stack.pop()

        switch(stackFrame.resumPoint){
        case init:
            if(baseCase){
                finalize
                break;
            }
            body1
            stack.push({resum1, params, variables})
            stack.push({init, modified_params})
            break;
        case resum1:
            body2
            stack.push({resum2, params, variables})
            stack.push({init, modified_params})
            break;
        case resum2:
            body3
            break;
        }
    }
}

Nything that can be done with recursion that can’t be done with loops

Yes and no. Ultimately, there's nothing recursion can compute that looping can't, but looping takes a lot more plumbing. Therefore, the one thing recursion can do that loops can't is make some tasks super easy.

Take walking a tree. Walking a tree with recursion is stupid-easy. It's the most natural thing in the world. Walking a tree with loops is a lot less straightforward. You have to maintain a stack or some other data structure to keep track of what you've done.

Often, the recursive solution to a problem is prettier. That's a technical term, and it matters.

Best Answer

Related Solutions

Algorithms – How to Convert Loop to Recursion or Vice Versa

Nything that can be done with recursion that can’t be done with loops

Related Topic