A tale of a tale of a tale of a tale of Recursion

You can only understand this meme if you were on the internet in the mid 00's.

Some say you need to understand recursion before you can understand recursion. You know what, let’s prove them wrong. I’ll try to explain how recursion works, and maybe, if you understand how it works, you will be able to understand how it works. Are you confused yet? I hope not, because we’re about to go deep down the rabbit hole.

TL;DR: Recursion is a function that calls itself. Yeah, that easy.

But wait, why is that useful? Can’t we do the same thing with loops? Well. Technically… yes. But where’s the fun in that?

Some actions are more suited than others to recursive implementations. You’ll want 1/ a simple operation whose sole purpose is to be repeated, until 2/ you meet an exit condition that will stop the recursion and cascade the results all the way back up to the first function call.

I know that example has been beaten to death, but recursion is a bit like the movie Inception. You get a function call, in a function call, in an function call, until you meet an exit condition and start climbing back to reality (= the rest of your program) all the way through every nested level of the recursion.

Let’s try to find an example. We need a simple operation that repeats itself until it meets a clear cut exit condition. The factorial function is perfect for that purpose. The factorial function is the multiplication of every integer from 0 to a given number. Factorial 3, for example, really expands to 3 x 2 x 1. So in summary, we’re trying to multiply our number, 3, by 3 - 1 . And then the result of that, by (3 - 1) - 1 and so on. People who aren’t funny at parties do it iteratively with loops. We’re gonna do it with recursion! Buckle up, you’re in for a ride!

int fact(int i)
{
    if (i == 0)
        return (1);
    if (i > 0)
        return (fact(i - 1));
} 

Let me explain. The second if is the main brains of our function. Basically, fact() will keep calling itself with i - 1 until it hits 0; when fact() is called with 0, it will for the first (and only) time enter the first if statement, which is our base case. This is our exit strategy. When our counter hits 0, we’ll return 1, and cause what I’ll call a “recursive return cascade”.

Here’s a graphic breakdown of what’s happening on the stack when we call fact(3) .

So, yeah. Recursion. You’ll understand it once you’ll understand it.