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 around the corner and says that the only key is hidden in a box. You are late for work and you really need to get into the room and take your shirt.


You open the box only to find ... even 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 to solve 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 some Javascript pseudo code that reflects what is happening (Pseudo code is written as code, but more like a human language).


functionlook_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)
      } elseif (item.is_a_key()) {
        console.log("found the key!")
      }
    }
  }
}

Another approach uses recursion. Remember, recursion is when a function calls itself. Here is the second option in pseudo code:


functionlook_for_key(box) {
  for (item in box) {
    if (item.is_a_box()) {
      look_for_key(item);
    } elseif (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 loops will work faster, but simplicity of recursion is sometimes preferable.


Since recursion is used in many algorithms, it is 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 count function. You can write it recursively in Javascript, for example:

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


This function will count indefinitely. So, if you suddenly run the code with an infinite loop, stop it with the Ctrl-C shortcut. (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 it needs to stop. There are always two cases in a recursive function: recursive and boundary cases. A recursive case is when a function calls itself, and a boundary case is when a function ceases to call itself. The presence of a boundary case prevents looping.


And again, the count function, only with a boundary case:

functioncountdown(i) {
  console.log(i)
  if (i <= 1) {  // base casereturn;  
  } 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 the function and pass the number 5 to it.


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


We will output the number 4. And again i is not less than or equal to 1, so we go to the else block and pass the number 3. This continues until i becomes equal to 1. And when this happens we will output 1 to the console and i will become less or equals 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. This is like a stack of books, you add one thing at a time. Then, when you are ready to take something back, you always take off the top element.


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


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

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



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


Have you found the key already?


Let's get back to the initial example of finding a key in boxes. Remember the first was an iterative approach using loops? According to this approach, you create a stack of boxes for searching, so you always know which boxes you have not searched in yet.



But there is no stack in the recursive approach. So how then does the algorithm understand which box to look for? Answer: A “stack of boxes” is stored on the stack. A stack is formed of half-executed calls to the function, each of which contains its own half-completed list of boxes for viewing. The stack keeps track of the 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 recursion video. It should enhance understanding of the concepts presented here.



Conclusion from the author


Hopefully this article has added a bit more clarity to your understanding of recursion in programming. The article was based on a lesson in my new Manning Publications video course called Algorithms in Motion . Both the course and the article were written according to the wonderful book “Grokking Algorithms” , authored by Adit Bhargava, by whom all these wonderful illustrations were drawn.


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


I want to add on my own that I am watching Beau Carnes articles and video tutorials with interest, and I hope that you also liked the article, and in particular these really wonderful illustrations from A. Bhargav's Grokking Algorithms.


Also popular now: