UNDERSTAND RECURSION

Demystifying Recursion

A New Way of Visioning to Help You Really Understand How Recursion Works

Photo by Christophe Hautier on Unsplash

Recursion is a very important concept in programming that you must master in order to efficiently deal with data structure when writing algorithms and solving problems.

Many of us find the concept of recursion difficult, though, and struggle a lot before fully getting it.

But when everything begins to just click, dealing with recursion becomes so fun and exciting.

Now, how can you make recursion “just click” for you?

In this article, I will introduce a fascinating (new) way of looking at recursion to help you master it. If you don’t like recursion and feel like wanting to avoid writing recursive functions if possible (as I have previously), my goal is to make you want to write recursive functions from now on even in your sleep!

Recursion vs. Iteration

Let’s recap what we already know first. What is recursion?

→ Simply, recursion is a loop.

Recursion is almost always compared to iteration, which is also a loop. If recursion and iteration are both loops, how are they different?

Let’s look at two of the most prominent differences between recursion and iteration:

1. Recursion takes additional stack space — We know that recursion takes extra memory stack space for each recursive calls, thus potentially having larger space complexity vs. iteration.
2. Recursion enables cleaner, more readable code — Despite requiring more space, using recursion can allow your code to be a lot more readable vs. iteration.

But we already know these differences and they don’t really help on actually understanding how recursion really works, right?

What is the real, most important difference between recursion and iteration that will let us more fully grasp how recursion really works?

To answer this, we need to understand the two phases of recursion.

The Two Phases of Recursion

Note, that the two phases that we are going to look at is not the two cases of recursion that we are familiar with:

• the base case
• the recursive case

Recursion is a function that repeatedly calls itself in smaller forms with the idea that a complex problem can be solved more easily by solving a smaller version of the same problem.

What recursion is doing is repeated calling a smaller and smaller version of itself, until you have the smallest possible case that is so small that you can simply solve it immediately → this smallest case is the base case. Then you use the answer to this base case to answer the next smallest problem, and then the next, and then the next, and so on, until you are back to the original problem that you began with.

Did you notice the two phases of recursion?

• We have one phase going toward the base case.
• We have another phase coming back from the base case.

The first phase of going from the original recursive call toward the base case is called the calling phase.

The second phase of coming back from the base case to the original recursive call is called the returning phase.

This is the main difference between recursion and iteration:

Iteration only has a calling phase, while recursion has a calling phase and a returning phase.

The reason recursion is difficult to fully grasp at first, is that the loop of recursion has two phases, and this makes it difficult to see the full combining effect of each recursive call’s results into the final result.

For iteration, this is simple because the loop goes just one way → you simply do the same thing in every iteration, period.

Note, in the above diagram, I have denoted “op” for each iteration to show that each iteration performs an operation that is immediately reflected in the code.

For recursion, I have denoted “op” with a question mark. This is because in recursion, we have two phases and a recursive call’s operation can be performed either in the calling phase or in the returning phase, depending on how the recursion function is designed.

• When operations are performed in the calling phase, they are performed as soon as the recursive call is made. This is similar to how iteration works. The operation is done first, and then its inner recursive call is made.
• When the operation is performed in the returning phase, recursive calls are made first. When a recursive call is made, it first calls its inner recursive call, which calls its own inner recursive call, and so on until the final recursive call with the base case is made. Then, as the recursion returns back toward the original recursive call, operations for each recursive call that have been waiting for the preceding recursive call operation to terminate, are now performed.

Here is the key to fully understanding how the results of each recursive call is combined into the final result: we need to understand WHEN the operations of each recursive call is performed.

Before diving into how recursion works in code, let’s take a moment to more fully grasp recursion and its two phases conceptually through a fascinating analogy.

Recursion is like Inception

If you have watched the movie Inception, you will notice a striking similarity between recursion and inception. Dream within a dream within a dream vs. recursive call within a recursive call within a recursive call.

With a specific goal in mind, you devise a dream and go into it. Inside that dream, you create another dream and go into that, and then another dream inside that dream, and so on until you go into an innermost dream. This is the calling phase, or going-into-the-dreams phase. The innermost dream is the base case.

Now, to achieve your goals and live a happy life back in reality, you have to come out of the dreams. You must first awake from the innermost dream, then the dream above that, and then the one above that, and so on until you are finally back out into reality. This is the returning phase, or coming-back-to-reality phase.

How the final result of the recursion is achieved depends on how the operations of each recursion call are performed.

There can be two ways to achieve your goals through inception.

• You can perform the necessary operations for each dream as you go in to the innermost dream. When you have reached the innermost dream, you have already done all of the necessary operations for each dream. All you need to do now is to simply awake from each dream like bam bam bam until you are back out into reality. Notice the order of goals achieved: the goal for the outermost dream is achieved first and the innermost dream last.
• Or, you can first go into the innermost dream by entering through all the dreams, and then perform necessary operations as you awake from the dreams. After achieving your goal for the innermost dream, you awake from that dream. Inside the next dream, you again perform your necessary operations and achieve your goal for that dream. You will continue these operations for each dream until you are awake from the last dream that you began with, and back out into reality. Notice the order of goals achieved: the goal for the innermost dream is achieved first and the outermost dream last.
• You can also combine these two ways. You can perform some operations on your way into inner dreams and perform some others as you come out of the dreams. For example, you can set up some bombs in a dream on your way into the innermost dream, and then as you awake from the dreams and reach this dream again on your way out to reality, you can trigger the bomb to explode.

What you can notice in this inception analogy is that how the inception is designed (or how the recursion is designed) affects how your goal is achieved. To put it another way, your inception or recursion function should be designed in a specific way, including the timing of operations, to achieve your intended goals.

Recursion in Code

Now, let’s look at how recursion actually works in code.

The examples I will be using are in JavaScript, but the language shouldn’t really matter in understanding how recursion works.

Iteration

First, let’s consider the following iteration function:

This is an iterative loop that will perform an operation (printing n) beginning with n = 6 and for each decrementing n, as long as n > 0. When n = 0, the loop breaks and your iteration is done.

The result of this while loop would be: 6 5 4 3 2 1.

iteration tracing

Tail Recursion

This same result can be implemented using recursion as follows:

The first recursion call is made with recursion(6). As long as n > 0, it will print n and then call the next recursive call. recursion(6) prints 6 and then calls recursion(5). This call will print 5 and then call recursion(4). This process will continue until recursion(0) is called. When recursion(0) is called, n = 0, so the recursive call terminates without performing anything. Since recursion(0) has terminated, we are now back at recursion(1) call, which have already performed its operation (printing 1) before calling recursion(0). Since both operations (console.log(1) & recursion(0)) of recursion(1) are now finished, recursion(1) terminates and we are now back at recursion(2) call. This continues until we return back to recursion(6), after which our recursion is done.

The result of the recursion would be: 6 5 4 3 2 1.

tail recursion tracing

Notice how all the necessary operations were already performed when we have reached the base case recursive call of recursion(0). All the operations are performed in the calling phase. As we return back from the base case in the returning phase, nothing else is actually done except simply terminating each recursive call.

This is an example of tail recursion. Tail recursion is a type of recursion in which the recursive call is the LAST operation of the recursive function, as in the above example. In tail recursion, all operations are performed in the calling phase and nothing is done in the returning phase except for simply terminating the calls.

Tail recursion is similar to iteration.

When you have a tail recursion, it is more efficient to write the code as an iteration, since they basically work the same way, but iteration has better space complexity.

Remember all recursive functions can be written in iterative form and vice versa, but in some cases it is more difficult to write a recursive function in iterative form.

Tail recursion is an example of recursion that can be easily written in iterative form, and in such cases, you should definitely write the code in iterative form and save memory space.

Head Recursion

Now, let’s take the above example and make it a head recursion instead, in which all operations are performed in the returning phase:

Notice how everything is the same, except for the order of the two recursive case operations (console.log(n) and recursion(n — 1)).

In this recursion, the first recursion call recursion(6) is made. Since n = 6 > 0, recursion(5) is made. Notice that console.log(5) can only be performed after the recursion(5) call is fully processed. recursion(5) must call recursion(4) , which must call recursion(3) and so on until recursion(0) is called. Since n is now equal to 0, base case is reached and recursion(0) terminates without doing anything. Now we are back at recursion(1) call. Here, notice how we have NOT yet performed the console.log(1) operation, because we needed to first wait for the recursion(0) call to terminate. With recursion(0) now fully processed, console.log(1) operation is performed. 1 is printed. recursion(1) is now terminated and we are back at recursion(2) call. Again, we haven’t yet performed console.log(2), so it is performed now. 2 is printed. recursion(2) is now terminated and we are back at recursion(3). This continues until we are back to recursion(6), which prints 6 and the recursion is done.

The result of this recursion would be: 1 2 3 4 5 6.

head recursion tracing

This is a head recursion. Head recursion is a type of recursion in which the recursive call is the FIRST operation of the recursive function. In a head recursion, all operations are performed in the returning phase.

Unlike tail recursions, head recursions cannot be easily converted to iteration.

If we were to write this head recursion in iterative form, we need to write it in such a way that the result will be 1 2 3 4 5 6.

If we write the above head recursion code in exactly the same order in iterative form, we would have the following:

The result of the above iteration function would be: 5 4 3 2 1 0. This is not what we were trying to get.

To get 1 2 3 4 5 6, we have to find a different way to write the iteration function:

The above iteration will give the desired result: 1 2 3 4 5 6.

But, unlike tail recursion, it is more difficult to write head recursion in an iterative form, although it is possible.

A More Complex Recursion Example

Now, let’s look at the following recursion function:

Here, we have a combination of operations performed in the calling phase and in returning phase.

This recursion is definitely more complex, but using our understanding of the operations performed in the two phases of recursion, we can make sense of how this recursion would return the final result.

Here is a simple rule for when an operation in a recursive function is performed:

1. Anything that comes before the recursive call is performed in the calling phase

2. Anything that comes after the recursive call is performed in the returning phase

In the above example, console.log(n) is performed in the calling phase.

+ n and thus the result variable initialization to recursion(n — 1) + n , and return result are all performed in the returning phase.

The first part is basically the same as the tail recursion example we have seen before:

console.log(n) is performed in the calling phase, so when we have reached the base case call of recursion(0), our recursion function would have already printed: 6 5 4 3 2 1.

Now, we have to look at the operations performed in the returning phase:

• At recursion(0), since n = 0, the base case operation that is outside the recursive block is performed: return 0. The return value for recursion(0) is 0.
• Now we are back to recursion(1). Since we now have the return value from recursion(1 — 1) = recursion(0), which is 0, we have:

const result = 0 + 1 = 1.

return result = return 1. The return value for recursion(1) is 1.

• Now we are back to recursion(2).

const result = 1 + 2 = 3.

return result = return 3. The return value for recursion(2) is 3.

• Now we are back to recursion(3).

const result = 3 + 3 = 6.

return result = return 6. The return value for recursion(3) is 6.

• Now we are back to recursion(4).

const result = 6 + 4 = 10.

return result = return 10. The return value for recursion(4) is 10.

• Now we are back to recursion(5).

const result = 10 + 5 = 15.

return result = return 15. The return value for recursion(5) is 15.

• Now we are back to recursion(6).

const result = 15 + 6 = 21.

return result = return 21. The return value for recursion(6) is 21.

We are done.

The final result of the above recursive function is thus:

6 5 4 3 2 1 (performed in the calling phase)

21 (the final result of operations performed in the returning phase)

Wasn’t that really simple?

By separating recursion into the calling phase and returning phase and looking at the operations performed in each phase one by one, we can more easily trace how the recursion is implemented.

There are more complex forms of recursion, of course, including tree recursions, indirect recursions, and nested recursions, but if you just remember that recursion has operations performed in the calling phase and those performed in the returning phase and if you just trace each operation one by one, you should be able to make sense of how the entire recursion is implemented to return the final result.

I hope this article was helpful in making a better sense how recursion works! Thanks for reading and good luck to all your programming endeavors.

Happy coding!