How recursion works - explanation in flowcharts and video

I present to you the translation of the article Beau Carnes How Recursion Works - explained with flowcharts and a video .

“In order to understand recursion, you must first understand recursion”

Recursion is sometimes difficult to understand, especially for beginners in programming. Simply put, recursion is a function that calls itself. But let's try to explain with an example.

Imagine that you are trying to open the door to the bedroom, and it is closed. Your three-year-old son appears from the corner and says that the only key is hidden in the box. You are late for work and you really need to get into the room and take your shirt.

You open the box just to find ... more boxes. The boxes are inside the boxes and you don't know which one is your key. You urgently need a shirt, so you need to come up with a good algorithm and find the key.

There are two main approaches to creating an algorithm for solving this problem: iterative and recursive. Here are the flowcharts of these approaches:

Which approach is easier for you?

The first approach uses a while loop. Those. while the stack of boxes is full, grab the next box and look inside it. Below is a bit of pseudocode in Javascript, which reflects what is happening (Pseudocode is written as code, but more like a human language).

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } } } 

In another approach, recursion is used. Remember, recursion is when a function calls itself. Here is the second option in pseudocode:

 function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } } 

Both approaches do the same thing. The main point in using the recursive approach is that once you understand, you can easily read it. In reality, there is no performance gain from using recursion. Sometimes an iterative approach with cycles will work faster, but simplicity of recursion is sometimes preferable.

Since recursion is used in many algorithms, it is very important to understand how it works. If recursion still doesn't seem easy to you, don't worry: I'm going to go through a few more examples.

Boundary and recursive case

What you need to take into account when writing a recursive function is an infinite loop, i.e. when a function calls itself ... and can never stop.
Suppose you want to write a counting function. You can write it recursively in Javascript, for example:
')

 // WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1) } countdown(5); // This is the initial call to the function. 

This function will count to infinity. So, if you suddenly run the code with an infinite loop, stop it with the key combination "Ctrl-C". (Or, working for example in CodePen, this can be done by adding “? Turn_off_js = true” at the end of the URL.)

A recursive function should always know when to stop. In a recursive function, there are always two cases: the recursive and the boundary cases. The recursive case is when the function calls itself, and the boundary case when the function stops calling itself. The presence of a boundary case and prevents looping.

And again, the counting function, only with the boundary case:

 function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1) } } countdown(5); // This is the initial call to the function. 

What happens in this function may not be completely obvious. I will explain what happens when you call a function and pass the number 5 into it.

First we will display the number 5 using the Console.Log command. Since 5 is not less than or equal to 1, then we move to the else block. Here we call the function again and pass the number 4 into it (since 5 - 1 = 4).

We output the number 4. And again i is not less than or equal to 1, so we go to the else block and transfer the number 3. This continues until i becomes 1. And when this happens we output 1 to the console and i becomes less or equal to 1. Finally we go into the block with the keyword return and exit the function.

Call stack

Recursive functions use the so-called Call Stack. When a program calls a function, the function is sent to the top of the call stack. It looks like a stack of books, you add one thing at a time. Then, when you are ready to remove something back, you always remove the top element.

I will show you the call stack in action using the factorial counting function. Factorial (5) is written as 5! and is calculated as 5! = 5 * 4 * 3 * 2 * 1 . Here is a recursive function to calculate the factorial of a number:

 function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } } 

Now, let's see what happens when you call fact (3) . Below is an illustration which shows step by step what happens on the stack. The topmost box in the stack tells you what to call the fact function that you are currently stopping at:

Noticed how each call to the fact function contains its own copy of x. This is a very important condition for recursion work. You cannot access another copy of the function from x .

Have you already found the key?

Let's briefly go back to the original example of finding the key in the boxes. Remember that the first was an iterative approach using cycles? According to this approach, you create a stack of search boxes, so you always know in which boxes you have not searched.

But in the recursive approach there is no stack. So how then does the algorithm understand which box to look for? Answer: The “stack of boxes” is stored on the stack. A stack is formed from half-executed function calls, each of which contains its half-completed list of boxes for viewing. The stack keeps track of a stack of boxes for you!

And so, thanks to the recursion, you were finally able to find your key and take the shirt!

You can also watch my five-minute video about recursion. It should reinforce the understanding of the concepts presented here.

Conclusion from the author

I hope the article has brought a little more clarity to your understanding of recursion in programming. The article was based on a lesson in my new video course from Manning Publications called “Algorithms in Motion” . Both the course and the article are written according to the remarkable book “Grokking Algorithms” , the author of which is Adit Bhargava, and all these wonderful illustrations were drawn.

And finally, to really consolidate your knowledge of recursion, you should read this article at least once more.

From myself I want to add that I am watching with interest the articles and video tutorials of Beau Carnes, and I hope that you also liked the article and especially these really wonderful illustrations from the book A. Bhargav “Grokking Algorithms”.