Recursion is probably the most tricky concept among not only programming newbies but also professionals. Causing a lot of troubles for programmers when
trying to understand it. Recursion, however is used in more advanced concepts of the programming, like many algorithms, so understanding this concept is essential to getting deeper into the waters of the CS.
That’s why we are going to split this concept into digestible parts and use creative analogies for you to understand it after one article!
Let’s start with a typical joke about the dictionary definition of recursion: “recursion: (n) see recursion”.
Another funny definition of recursion is that it is a function that calls itself again and again and again until it stops.
The most trivial, but powerful example of the recursion of all times
To illustrate recursion, and explain you the jokes, let’s imagine that we are looking for the
meaning of a word on the Internet. After entering wikipedia, however, we see some not-so-good explanation and a link that takes us to the same page. You are clicking the link expecting to find out more, however you are taken back to the same page. You are getting angry, then and you start clicking this link over and over again. In the end you get an error instead of the page. This process (clicking on the link until the error occurs) is a kind of recursion. Error was triggered by some condition, technically we call it the base case.
Definition of the recursion in programming
In programming, recursion is a process that calls itself until a condition (base case) is met. Base case prevents the recursion from calling itself again until so called stack overflow. The word condition or a base case is the key. I’m repeating it on purpose, as forgetting it is a common thing. If we implement recursion in the way that program never ends, it will lead to the aforementioned stack overflow – yes – now you know where the name of the popular forum comes from. Stack overflow in simple terms it is the moment when we ran out of the computer’s memory (RAM).
The best analogy of the recursion I’ve ever heard of
Another example for remembering recursion even better is the parable of the boy and the old man. Once upon a time in a village, people were playing Blackjack. Among peasant there was a boy that came up with an idea of calculating how many tries it would take him to sum up to 21 summing up numbers in the sequence the way that each number is equal to the sum of two numbers before it. However he was still young and didn’t know the math. Everyone in the village was captivated by the Blackjack and all the tries of asking for help ended up with “Go away boy, gambling is not for kids”. However nearby the village lived a wise old man. The boy went to him and ask for help with his equation.
Domenico Ghirlandaio
Unfortunately it happened that the old man, was suffering of alzheimer and couldn’t add more than two numbers at a time. Every time giving the boy a sum of two numbers he remembered only that he was already tired and was sending the boy away.
But the yound mathematician was desperate, so he was comming to the old man once in a while and asking him consecutively:
to add 0 and 1. “1“was answered by the old man.
Peasant write down 1, then let the old man to rest.
Then after a while he came back to the oldie and asked: “1 + 1“.
“2” The old man replied.
After a while: “2 + 1” (sum of the previous two numbers [1 + 1] plus previous number in created sentence [1]).
“3” the oldie replied.
“2 + 3“, “5“.
“3 + 5“, “8“.
“8 + 5“, “13“.
“13 + 8″, “21”.
At this time there were no numbers left.
“Okay, I’m done” said boy.
“And we wen’t through the whole recursion” muttered under his breath the old man.
For you to have it clear, the process of comming back and asking is a recursion and the sum being equal to 21 was the boy’s base case than ended it (recursion).
Recursion sometimes is a natural choice
Many programming problems are of such a nature that solving them recursively is simply natural. Because recursion is a technique used to solve problems by breaking them down into smaller sub-problems that when solved solve the big one step by step “recursively”. Example of such problem is the Fibonacci sequence. Exactly the one that I brought to you through the story of the boy and the old man. Recursion it is a foundation of many useful techniques like divide-and-conquer, decrease-and-conquer and even domain called dynamic programming. Besides many of mathematical computations, there are more examples of the application of recursion like many of the sorting algorithms, backtracking or syntax analysis of programming languages. There are even recursively defined data structures – trees. That are present in concepts like DOM or in managing directories of your operating system.
Implementation of the recursion
Now that I’ve given you a break from analyzing practical examples, let’s now move on to implementing our Fibbonaci sequence using recursion.
Remember that you can try underneath examples by copying and pasting code to the chrome’s/mozilla’s development console (F12 -> console).
function fibonacci(num) {
if (num <= 0) return 0;
if (num === 1) return 1;
return fibonacci(num - 2) + fibonacci(num - 1);
}
console.log(fibonacci(7)); // Output: 13Explanation of the recursive Fibonacci sequence
As we can see, the fibonacci function returns the sum of two calls to itself. To understand what is going on in it, let’s put some values into it. Suppose we call a function with the number 3. fibonacci(3) first checks if the number passed is less than or equal to one. In our case, 3 does not satisfy this condition, so we move
on.
The function then returns the sum of calls to itself. The first call, let’s call it the left call, is called with the number minus 2, the second call, let’s call it the right call, calls itself with the number minus 1. Let’s deal with the left call first, pass it our starting number. For us it will be 3 so we will pass the number 3 – 2 to the
left call.
Now we go through the previous steps again but with the number 1. First, we check if 1 is less than or equal to 1. It is, so we return 1. So for the ‘left’ execution, instead of fibonacci(number -2) we cancbet 1. Now we are left with the line return 1 + fibonacci(number – 1). We only have the right call left to
solve. So we give it the number 3 – 1. So 2. Now we go through the whole process with the number 2. First we check if it is equal to or less than 1, then we ‘divide’ it into two consecutive calls. In subsequent calls, the results will be 1 and 1. Since 2-2 = 0 and 2 – 1 = 1. Therefore, we end these ‘loops’ of recursion with a
return of 0 + 1. We can also change our ‘right’ execution to 1. As a result, we have the lines return 1 (from the left execution) + 1 (from the right execution). We are left with the result return 1 + 1. So the function fibbonaci(3) returns the number 2.
For better understanding here’s is a list of calls of all the subfunctions in order they are being run:
fibonacci(3) = fibonacci(2) + fibonacci(1)
Left side of the Fibonacci calls:
fibonacci(2) = (fibonacci(1) + fibonacci(0)) + fibonacci(1)
Right side of the Fibonacc calls:
fibonacci(1)
In mathematical terms:
fibonacci(3) = 1 + 0 + 1 = 2
Visual representation of the recursive Fibonacci
Looking at everything what was written, we can see the tree structure of the Fibbonaci sequence:
f(3) = f(2) + f(1) = f(1) + f(0) + f(1) = 1 + 0 + 1 = 2
Recursive thinking
Recursion involves breaking down problems into smaller ones and then solving everything “bottom up”. This recursive breaking process is sometimes called “recursive thinking”. For solving recursive problems it is often recommended to use the following formula:
- Assume you already have a function that solves your problem.
- See how big a problem can be solved by breaking it down and solving one (or more) small problems.
- Solve these problems using the imaginary function from step 1.
- Decide what your base cases are (conditions that stop further calls).
- Base cases must be so simple that they can solve themselves without further calls.
Summary of the recursion in programming
Recursion is a process that calls itself until a given condition. You can imagine it as clicking the link that takes you to the same page over and over until an error occurs. The mental process we use recursive to solve recursive problems is called recursive thinking. In recursive thinking, we break a problem down into smaller ones and solve them over and over again from the bottom up until we solve the whole problem. There are many techniques related to recursion, such as Decrease and conquer, divide and conquer, and even domain called dynamic programming.
PS of the recursion in programming
The BigO of the Fibonacci example that I used above is equal to O(n^2). If you would like to know more about Big O Notation you can read this article.
If you would like to know more about the backstage of stack overflow, I recommend you this article.
Thanks for your time!
Patryk
Senior Software Engineer with over 7 years of experience and entrepreneurial background. Most often, apart from delivering good quality code on time, responsible for introducing good practices, teaching programmers and building team bonds andestablishing communication on the line of development-management. Privately Kākāpō and Wombat enthusiast, traveler and retired acrobat.