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

Raymond Price — Sun, 29 Nov 2020 02:49:36 +0000

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);
}

or the Fibonacci sequence

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

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)

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, 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(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.

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 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;
}

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];
}

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);
}

Conclusion

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

Project Ideas

Raymond Price — Sat, 09 May 2020 00:04:14 +0000

So, you've decided to take this time in quarantine to learn to code, and now you need some projects to practice on? Cool beans, here are some ideas to get you started. This is going to bias towards web development, just because that's what I do, but these ideas should work just as well for desktop and mobile development.

Talk to family and friends about problems they need solved. Does your mother need some way to digitize and organize her old recipe cards? Would your uncle like some way to play euchre with his friend across the country? How hard would your baby brother giggle if you made a Discord bot that just responds to any post that includes "69" with "Nice."? If you have an actual human problem that you're solving, you're more likely to actually see it through to completion than if you just have a piece of homework that you can shelve as soon as you think you've learned enough. No I do not have a dozen unfinished projects cluttering up my Github, why do you ask?
Create a CRUD app. CRUD, for the ignorant, stands for Create, Read, Update, Delete, the 4 basic operations with databases, and refers to anything that can be reduced to messing around with a list of data. These apps include, but are by no means limited to,
- A website that shows a random joke/fact/cat picture from its database on each view, and optionally includes a permanent link for each item so users can share them with friends.
- A journal app, optionally including push/email notifications to remind your user to make an entry for the day.
- A budget tracker, possibly attaching to bank APIs to read the day's transactions.
- A catalog of the media in your collections, optionally interacting with eg IMDB to properly identify your media.
- A workout/diet tracker, optionally including analysis of each day's caloric and nutritional intake.
- A poll/survey site, optionally including stats/charts and the ability to create new polls.
- A recipe database, optionally including search-by-ingredient capability.
Implement a (simple) game. Obviously this one is going to be largely up to you, but the less you have to track, the simpler the game is to implement, particularly if you don't have to track it in real-time. For optional challenge, you can include a leaderboard, a better AI, a human opponent.
Clone your favorite website. A lot of websites, including Twitter, Spotify, Github, Reddit and others, have semi-public APIs you can access to make your own clones of their website. You can also build on those APIs to add your own special features, like a list of your most-played songs on Spotify.
Create a form-filler. The classic example here is a resume generator, where you enter your name, experience, education, etc, and get out a neatly formatted resume in whatever layout and format you need. You can also use this sort of thing for making RPG characters, planning a build in a computer game, or possibly even doing your taxes, although I would advise caution on that last.
Misc-
- A drawing app
- A real-time chat app
- Something with image manipulation, like maybe a meme creator
- A timer app, either as a simple stopwatch/alarm clock, or for Pomodoro purposes
- A forum engine
- A blog engine
- A calculator, scientific or otherwise. This may interact with the form-filler above, if you need to work out how much HP an orcish barbarian gets from one more point of constitution.

If none of these ideas really speak to your very soul, you can search through the "ideas", "project", and "projects" tags here on DEV.to to find other ideas you like better. Happy coding!

DEV Community: Raymond Price

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