DEV Community

loading...

What is Recursion, and Why Shouldn't You Use It?

darthbob88 profile image Raymond Price ・4 min read

What is Recursion?

Recursion is, simply, when a function calls itself. This makes writing some functions a lot simpler. We can write a factorial function like so

function factorial(number) {
    if (number == 1)
        return 1;
    return number * factorial(number - 1);
}
Enter fullscreen mode Exit fullscreen mode

or the Fibonacci sequence

function fib(number) {
    if (number == 0 || number == 1)
        return number;
    return fib(number - 1) + fib(number - 2)
}
Enter fullscreen mode Exit fullscreen mode

or we can use recursion to traverse trees

function traverse(rootNode) {
    if (rootNode != null) {
        traverse(rootNode.left);
        traverse(rootNode.right);
        doSomethingWith(rootNode);
    }
}
// called like traverse(someTree.root)
Enter fullscreen mode Exit fullscreen mode

as well as lists, and file systems, but those are a little more complicated than I want to get into right now and factorial/Fibonacci/tree will suffice for this demonstration.

Why Shouldn't You Use It?

The simplest problem with recursion is repetition of sub problems; calculating fib(10) requires calculating fib(9) and fib(8), but calculating fib(9) requires fib(8) and fib(7), which is already unpleasant repetition. In fact, if you instrument that function like so (which you shouldn't do, because it's a foolish method, but it'll work for this demonstration)

var numberOfCalculations = new Array(11).fill(0);
function fib(number) {
    numberOfCalculations[number]++;
    if (number == 0 || number == 1)
        return number;
    return fib(number - 1) + fib(number - 2);
}
fib(10);
console.table(numberOfCalculations);
Enter fullscreen mode Exit fullscreen mode

you will find that we effectively calculated fib(1) 55 times just to get the 10th Fibonacci number. If you do that test for fib(20), that apparently requires calculating fib(1) over 6700 times. That is clearly shamefully inefficient.

The second problem is a matter of implementation. Most computers and languages put function calls on a call stack, where the computer says "Before I can calculate factorial(10), I need to calculate factorial(9), so I put factorial(10) on the stack to calculate later, and work on factorial(9). Before I can do factorial(9), I need to do factorial(8), so factorial(9) goes on the stack", and so on until it hits factorial(1), when it can finally return an actual result and resume calculating factorial(2/3/4/5/etc). That means calculating factorial(10) requires putting 9 intermediate calculations on the stack, a stack which has a very finite size. You can get away with that for factorial(10), and possibly even factorial(100), but factorial(1000) will crash your browser, or at least throw a stack overflow error.

Additionally, recursive solutions are often slower than a comparable iterative solution entirely because of the processing cost of doing that stack pushing and popping, but that's harder to demonstrate except by profiling.

What Should You Do About It?

First off, make sure you actually do need to do anything about it. Premature optimization is the root of all evil, after all. Even if it's slower, recursion is usually fast enough for most purposes. If you have determined that recursion is a problem, then proceed to solving it.

The "simplest" solution is just to do an iterative solution instead of a recursive one. The basic idea here is to replace the program call stack with your own explicit stack.

function traverse(rootNode) {
    const stack = [];
    stack.push(rootNode);
    while (stack.length > 0) {
        const currNode = stack.pop();
        if (currNode != null) {
            // Note that we reverse the order of the push, so node.left gets popped and processed before node.right 
            stack.push(rootNode.right);
            stack.push(rootNode.left);
            doSomethingWith(rootNode);
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

In some cases you can get away with skipping the stack straight to a for-/while-loop, but you can't rely on that.

function factorial(number) {
    let accumulator = 1;
    for (let ii = number; ii >= 1; ii--) {
        accumulator *= ii;
    }
    return accumulator;
}
//Or, more cleanly
function factorial(number) {
    let accumulator = 1;
    for (let ii = 1; ii <= number; ii++) {
        accumulator *= ii;
    }
    return accumulator;
}
Enter fullscreen mode Exit fullscreen mode

Another option is to memoize the function, where you store the results of expensive calculations for reuse. This carries the obvious tradeoff that it trades space for time, but it's often a good idea.

function fib(number) {
    var memoize = [];
    return fibrec(number, memoize);
}
function fibrec(number, memoize) {
    if (memoize[number] != null)
        return memoize[number];

    if (number == 0 || number == 1)
        return number;
    const result = fibrec(number - 1, memoize) + fibrec(number - 2, memoize);
    memoize[number] = result;
    return result;
}
Enter fullscreen mode Exit fullscreen mode

You can also combine those two methods for my favorite stupid Fibonacci method.

function fibiter (number) {
    const memoize = [0, 1];
    for (let ii = 2; ii <= number; ii++) {
        memoize[ii] = memoize[ii-1] + memoize[ii-2];
    }
    return memoize[number];
}
Enter fullscreen mode Exit fullscreen mode

A third option, which is implementation-dependent and only available in some languages, is tail-call optimization. This is writing a function so the recursive call is the very last thing executed before returning, which means that we don't need to store the calling state. The factorial function presented earlier in the article is not tail-call optimized because the calling function still has to do number * factorial(number - 1);, which means the calling function has to get stored on the stack.

function factorial(number) {
    return factorial_TCO(number, 1);
}
function factorial_TCO(number, accumulator) {
    if (number == 1)
        return accumulator;
    return factorial_TCO(number - 1, number * accumulator);
}
Enter fullscreen mode Exit fullscreen mode

Conclusion

Recursion is an extremely powerful tool, but you should be aware of its hazards and how to mitigate them.

Discussion

pic
Editor guide
Collapse
dcwither profile image
Devin Witherspoon

Hey, thanks for sharing! BTW, you can tag code blocks with a language to get syntax highlighting by adding the language extension (e.g. js, c, cpp, java) after the the first three backticks.
sample react component wrapped in backticks with javascript syntax highlighting

Collapse
darthbob88 profile image
Raymond Price Author

Much thanks, I was not aware of that and just added it to the article.

Collapse
shadowtime2000 profile image
shadowtime2000

People don't use recursion because they think it is fast. They usually use it because it fits with the functional programming paradigm which is growing more and more popular now a days.

Collapse
dmbaturin profile image
Daniil Baturin

It's a shame JS implementations still don't support tail call optimization. More and more JS is not written, but cross-compiled, and a lot of time the source language makes functional approach natural and easy to reason about.

Structural recursion is much easier to reason about than iteration, but you need TCO to make it fast, and most modern backends including .Net can already do it.

Collapse
darthbob88 profile image
Raymond Price Author

AFAIK ES2015 at the very least supports TCO as part of the spec, and allegedly the V8 implementation does support TCO, but I'm having a hard time finding any firm confirmation.

Collapse
darthbob88 profile image
Raymond Price Author

Well that, and it's often simpler and clearer than the iterative method. Compare the two versions of tree traversal in this article.

Collapse
chrisvillegas profile image
Chris Villegas

Yeah we shouldn't use design patterns nor anything that requires more than pasting code from stackoverflow. :)

Collapse
darthbob88 profile image
Collapse
lordnodd profile image
Ashwin

We use cache for such disadv, by storing pre-calculated fib(n) and checking if it exists, that way you avoid the hassle of calculating fib(1) 51 times.

Collapse
darthbob88 profile image
Raymond Price Author

Yeah, memoization. That's the second method I mentioned for mitigating the issues of recursion.