DEV Community

loading...
Cover image for Think recursion

Think recursion

jmau111 profile image Julien Maury Originally published at blog.julien-maury.dev Updated on ・3 min read

Recursion is a critical concept in computer science. It goes way beyond code, but you have to master it as a developer.

Smaller instances of the same problem

You split the problem into smaller instances of the same problem, and you make a recursive call of your solution.

When you call any function, it goes on top of the call stack. It is a list that keeps track of which function runs currently and what functions they call themselves.

Once your function has run, it leaves the stack, and the execution restarts where it left off.

Stacks vs. queues

We call it a stack because you can only add or remove elements on top of it. The last elements you add will be the first to leave (Last In First Out or LIFO).

On the contrary, a queue would be FIFO (First In First Out). The first element you add will be the first to leave.

It's vital to know the difference to understand recursion.

Why is it so efficient?

So we saw the last elements you add in the call stack are the first to leave. The crazy good part of all that stuff is that a recursion takes a constant time no matter how big your dataset is.

It's neither a linear nor a proportional relation. It's constant.

You can read about Big O notation to dig it.

"Stack overflow"

Unfortunately, it's possible to fail. You will probably experience that, especially with your first recursions.

We saw the call stack holds precious information such as the return addresses of your running functions. The stack is not infinite. If your recursion is too deep, it will take all the available space and crash everything.

In my article about memoization, I give a python example of that problem:


fiboCache = {}

def fibo(n):
    if n in fiboCache:
        return fiboCache[ n ]
    if n < 2:
        return 1
    fiboCache[ n ] = fibo(n - 1) + fibo(n - 2)
    return fiboCache[ n ]
Enter fullscreen mode Exit fullscreen mode

EDIT: I've changed the fibo code example with some code quality props to @vlasales because his version is shorter and thus better than mine, it's true we don't even need that intermediate value.

If we don't use a dictionary to store calculated values, the script keeps calling the same operations again and again (and again ^^). fibo(2) executes fibo(1). fibo(3) executes fibo(2) and fibo(1), but fibo(2) executes fibo(1) too, etc.

Recursion can be tricky. If you misuse it, you get a linear relation, which ruins everything.

What's the point of all that stuff?

IMHO, recursion is not optional for developers. Many job interviews include problems that are easy to solve with recursion and absolute nightmares without this concept.

It's not rare to have questions like that :

I have this colossal data structure (e.g., a big array) with tones of sub rows. I want all occurrences of specific data. The order can change. It's possible to remove and add lines.

How do you handle that? (Of course, we assume you have something to identify the expected data ^^).

Naive solutions would include some nested loops and pretty complex conditions. Not only that, those naive solutions are complicated and hard to read, but it takes a lot of time to code, and it may fail in some cases.

Paradoxically, recursion is more comfortable here.

Wrap up

I hope you understand a little more recursion and why it is almost everywhere in code, and why it's recurrent in job interviews.

Discussion (4)

pic
Editor guide
Collapse
vlasales profile image
Vlastimil Pospichal • Edited
fiboCache = {}

def fibo(n):
    if n in fiboCache:
        return fiboCache[n]
    if n < 2:
        return 1
    fiboCache[n] = fibo(n - 1) + fibo(n - 2)
    return fiboCache[n]
Collapse
jmau111 profile image
Julien Maury Author

I've updated post with this better version.

Collapse
Sloan, the sloth mascot
Comment deleted
Collapse
realedwintorres profile image
Edwin Torres

Nice article. I just wrote about my journey with recursion. You're right, it's all around us.
c0ffee2c0de.blogspot.com/2020/10/t...