What is Recursion, and Why Shouldn't You Use It?
Tags: concepts, recursion, javascript, algorithms
Published: 2020-11-29 02:49:36

---
title: What is Recursion, and Why Shouldn't You Use It?
published: true
description: An article against the evils of recursion
tags: concepts, recursion, javascript, algorithms
---

## What is Recursion?

Recursion is, simply, when a function calls itself. This makes writing some functions a lot simpler. We can write a [factorial](https://en.wikipedia.org/wiki/Factorial) function like so
```javascript
function factorial(number) {
    if (number == 1)
        return 1;
    return number * factorial(number - 1);
}
```
or the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number)
```javascript
function fib(number) {
    if (number == 0 || number == 1)
        return number;
    return fib(number - 1) + fib(number - 2)
}
```
or we can use recursion to traverse trees
```javascript
function traverse(rootNode) {
    if (rootNode != null) {
        traverse(rootNode.left);
        traverse(rootNode.right);
        doSomethingWith(rootNode);
    }
}
// called like traverse(someTree.root)
```
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)
```javascript
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);
```
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](https://en.wikipedia.org/wiki/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.
```javascript
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(currNode.right);
            stack.push(currNode.left);
            doSomethingWith(currNode);
        }
    }
}
```
In some cases you can get away with skipping the stack straight to a for-/while-loop, but you can't rely on that.
```javascript
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;
}
```

Another option is to [memoize](https://en.wikipedia.org/wiki/Memoization) 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.
```javascript
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;
}
```

You can also combine those two methods for my favorite stupid Fibonacci method.
```javascript
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];
}
```

A third option, which is implementation-dependent and only available in some languages, is [tail-call optimization](https://en.wikipediia.org/wiki/Tail_call). 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.
```javascript
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);
}
```
## Conclusion

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