To understand recursion, you first have to understand recursion.

As you may hear this phrase I’m sure you have heard another kind of metaphors or analogies to understand recursion in programming, one of them could be the matryoshkas dolls.

From the New Yorker, 04/10/10

But let’s tackle this without analogies, but concrete examples in programming.

What is recursion? according to Wikipedia is a method of solving a problem which it’s solution depends on solutions to smaller instances of the problem.

A practical way to see this is through a recursive function, what we will see here is that a function will act as a loop without using a while or a for. I will use a C language function to demonstrate it:

Here we have a power math operation represented in a recursive algorithm. In general terms a recursive function must have:

• A conditional where the iteration would stop

This will be the very first expression the function will run, so with this conditional, we will make sure it will exit the function at some point. Also, we have to make sure that the conditional we set has to be related to the problem logic.

• The function calling itself until the condition above is met:

here we have two expressions where the function could call itself.

As you may notice, the variable ‘y’ will change throughout the iterations. Why? because we are even adding or subtracting 1, depending on the conditional if (y < 0).

The behavior of this recursive function will be as a stack. Let’s see how it would look like in the following graphic.

I hope it was useful for your understanding. In case you want to dig more into this subject, I would suggest you reading further about programming paradigms, this method it’s related directly to the structured programming paradigm.