Follow me on Twitter, happy to take your suggestions on topics or improvements /Chris
Ok, a big picture of sheep. Now he really lost it or? Actually, it's an analogy to Recursion, a lot of similar function invocations, almost same same but different ;) If you read on you will see Recursion explained and a few problems solved even.
I'm writing a fundamentals series on Computer Science topics. Why you ask, why not the latest JS Framework or something similar?
Well, there is more than one reason, knowing the fundamentals is a timeless skill, regardless of what framework, language or library you learn, fundamentals will always be there.
Ok, that sound like a textbook answer, are we supposed to buy that?
There is more to it of course. I've been in the IT industry for more than a decade and what you find after using a ton of libraries and languages is that after a while you strive after expanding your mind, solve problems you haven't seen before or even solving the same ol problems but in a new way.
Is it fair to say you've just been solving problems, sometimes in a hacky way?
Yea, I think we all can testify to that, sometimes our solutions have been good and sometimes less so.
And if I'm being completely honest I wasn't the most attentive student at University and the more I look into things like Big O notation, algorithms, recursion, compilers and so on, the better it feels when I finally get it and appreciate its elegance.
So for that reason, I will start this series by covering Recursion, one of the Big Whales, one of the big concepts to conquer. I hope to show the following:
- What is Recursion
- Why Recursion, what problems it can be used for and why it can be a really elegant approach
- Problem solving We will show a series of problems where Recursion really shines and how to solve them
What is Recursion
One of the standing jokes of recursion is:
If you want to know what Recursion is, see Recursion
In short, recursion is a method calling itself a number of times.
That sounds like a
while-trueloop like we are going to run out of memory
Yup, that's one of the pitfalls of recursion, if you do it wrong you will see error messages looking like this:
Why
Why on earth would I want to be calling myself x number of times?
Well, it's about the nature of your problem. Some problems can be seen as a reoccuring pattern that you can apply the same solution to over and over.
Ok, you'll have to explain that better.
Sure we will show what we mean by working through a series of problems.
Ok fair enough but you still haven't explained the why?
In a word elegance, written correctly a recursive solution usually, consist of very few lines of code. This means our cognitive load for understanding and even modifying the code lowers drastically.
Ok I get that, everyone likes simple, what else?
Recursion is often used as a replacement for for-loops and while statements. It's in its very nature to loop or rather reapply it's logic. I think it's fair to say it has a divide and conquer approach. Not be confused with the actual divide and conquer. All I wanted to say here was that, we slowly conquer our problem by realizing that we are looking at a dataset full of patterns that look similar, self-similarity. This self-similarity makes it possible to apply the same algorithm over and over.
You REALLY have to explain that
Well, you start off working on a set of data that gradually decreases which means we work towards a point. Once we reach that point we consider the problem solved.
What type of problems can we solve?
Well, here is a non-exhaustive list, so you get a sense for it:
- summation, we can easily sum up all the items in a list
- power, calculate the power of something is the same as multiplying a number by itself x number of times
- factorial, factorial is about multiplying all numbers in a descending fashion
- trees, trees are used for a lot of things in Computer Science, like compilers, post-pre fix processing like a calculator, etc.
- conversion, for example, turning a string to a number
- sorting, recursion is often used to implement sorting algorithms like merge sort for example.
This is just a small subset of problems we can solve and yes you can solve most of the above with for loops and while constructs but that usually leads to messier code.
Solving some problems
You must be itching by now to see some code so let's first start off by showing what a typical recursion looks like:
function recursion(data) {
if(condition) {
return 'something'
} else {
recursion(data)
}
}
As you can see above we start with an IF clause, this is also called a base case or terminating condition. For you not to end up in a while-true condition you need to make sure that this condition is met.
Our ELSE statement is where we call ourselves again, as you can see we call the method recursion() again. The idea here is to modify it slightly so we ultimately reach our base case.
Let's look at some real problems next.
Factorial
In a factorial, the idea is to multiply all the numbers going up to and including the number itself. For number 5 that would mean we would need to compute it like so:
5 * 4 * 3 * 2 * 1
As we can see above we are working with a series of numbers that slowly descends towards a base condition 1. Let's see some code:
function factorial(num) {
if(num === 1) {
return 1;
} else {
return num * factorial(num -1);
}
}
I have to admit that the first time I saw a solution like this my head just exploded, I couldn't take it in, I was like is this even valid code or this would have been so much simpler using a for-loop like so:
function factorial(num) {
var sum = 1;
for(var i = num; i > 0; i--) {
sum *= i;
}
return sum;
}
I understand my past self and some of you reading this. Recursion hurts when you first look at it unless your brain is wired in a certain way ;).
So why is the recursive solution better? For me, at least, it's about simplicity. If we look at a specific row:
return num * factorial(num -1);
All we think about here is returning num and we leave the rest to its own computation when we call factorial() again and this time with an adjusted value of num. The hard bit to understand, for me, was that this was valid code. I could see that this would lead to a 5 * 4 * 3 * 2 * 1 scenario. I just didn't get that the compiler was OK with it. But it is, which leads us to our next problem.
Conversion, string to number
Now, this is an interesting one. What really happens when we convert something from "234" to 234. Well, it's an addition. It's 200 + 30 + 4. What does that look like?
A descending series?
Yes, exactly, but let's be even more detailed, it looks like the following:
2 * 10^2 + 3 * 10 ^ 1 + 4 * 10 ^ 0
Given what we learned from our factorial we can start sketching on it:
currentcharacter * Math.pow(10, pow) + convert(character)
Ok, we get roughly the how. The next question is what does our base condition look like? The answer is that we are working with one character only, like so:
if (chars.length === 1) {
return parseInt(chars[0]);
}
The above tells us that we will process our number from left to write and as soon as we process the leftmost character, it's considered processed and we should keep working on a smaller dataset. It's crucial that we make the dataset smaller so we reach our base condition. So let's see the rest of the code:
function convert(num) {
let chars = (num + '');
if(chars.length === 1) {
return parseInt(chars[0])
} else {
let pow = chars.length -1;
return Math.pow(10, pow) * parseInt(chars[0]) + convert(num.substr(1));
}
}
Zooming in our else condition:
else {
let pow = chars.length -1;
return Math.pow(10, pow) * parseInt(chars[0]) + convert(num.substr(1));
}
We can see that we apply our descending pattern of 2* 10^2 + 3* 10^1 + 4 or "234" turns into 234. The reason it's descending is that we do this:
convert(num.substr(1))
We pick off one character from the left so 234, becomes 34 and finally 4 and thereby we reach our base condition.
Summary
I could be showing you trees and a ton of other implementations but let's stop here. Have a look at this repo in which I've solved some more problems with recursion. The point I wanted to get across was what recursion is, why it for certain problems constitute a simpler and more elegant solution and I of course also wanted to explain the building blocks of recursion and how to think when solving such problems.
I hope it was educational. If you want me to write a follow-up article on this topic let me know in the comments.
You might not be convinced at the end of this that recursion is for you. I wasn't for the longest time. To be honest, I enjoy the pattern that comes with recursion. If part of your job is to write algorithms or if you got aspirations towards becoming the next Code Wars master or applying for a job at a famous tech firm, this is a thing you will need to know. If not, carry on, for-loops are part of the language too :)
Or as they say where I live:
Keep calm and carry on :)
Top comments (23)
Hi,
recursion is powerful, but it is also one of the algorithms that has the greatest possibility to screw-up a full server by creating an infinite loop. Infinite loops are bad.
So please, anytime you do recursion for something not trivial, please put a circuit breaker (i.e. if you go through recursion more than N times, N being big enough), stop processing and raise an error.
Couldn't one say the same of
whileloops?Well, there are two kinds of situations that can lead to infinite loop. The first one is that the algorithm is plain wrong. This is usually quickly detected and can happen in while loops also. A plain wrong algorithm typically does not make its way into production, so I am not too worried by those.
However, there is another situation, where the algorithm is in principle OK, but the data will make an infinite loop. This happens when what is supposed to be a tree actually contain loops of links. I have seen errors happen almost always on recursive algorithms.
I think it is good practice, for anything running on a server, to be robust to those situations. The circuit breaker is one plain easy way to implement this robustness.
So if you hit a cycle within a graph, in what way would
whilebehave better than a recursive call?Actually, you would not be able to go through a tree easily with a while. You would implement a recursive algorithm to do that.
you can mitigate the risk of infinite loop through
Well, traversal, at least, is straightforward to do iteratively with an explicit stack.
IMO "recursion should always be bounded" doesn't make for good advice. The risk of infinite loops is higher when iterating, because a recursive version has to stop once the call stack is blown. (Excepting tail calls in the handful of languages that optimize them.)
So I think that leaves us with "loops and recursion should always be bounded" -- which IMO isn't appropriate for most domains.
I do agree that cycle detection is useful. And I think you're saying that often when one encounters recursive code, it's doing something to a tree -- if so, I agree there too, depending on language. I also think that a forgotten base case doesn't stand out visually the way that
while(true)does.Even so, I don't think we can generalize from "trees can have accidental cycles" to "all recursion should come with a kill switch." I think the right advice is "don't forget the base case" and "do cycle detection as necessary."
Hi Nicholas. Thanks for the comment. That's a really good point..
Recursion is good but as the others say, it can bring a lot of problem if the programmer doesn't do it well, one of the problem it can create if the explosion of the call stack if the depth is too deep.
yep, seen that happen for sure. Like with all software some of it can be fixed by tests and sometimes it says something about your data that you didn't expect
Great post as always Chris. I had considered doing something similar myself as I had similar thought that after all these years I'm not actually sure I know the fundamentals or even use them on a daily basis anymore. Maybe it's all become second nature, I've no idea.
Looking forward to more posts!
To properly understand recursion, you should first understand recursion.
One good reason for recursion is that some data structures are defined recursively (lists, trees) and so operations on them can be described elegantly using recursion.
FWIW, I think reading The Little Schemer helped me the most for getting the mindset (though I still struggle with it sometimes -- the easy situations become easy over time, but I'm not sure recursive thinking ever becomes truly natural). It's a fun book; I love the quick question-and-answer format.
I won't link it here, but it's very easy to find a PDF online ;)
Be advised that divide and conquer has a specific meaning w/r/t algorithms. But I think what you're getting at is that recursion is a good way of dealing with self-similarity.
E.g. a list is either empty or it's an element followed by a list, so recursive list processing "collapses" down to those two cases.
I actually have some tree examples in here, github.com/softchris/recursion . I thought of adding those too, to the article but it would have been a lot longer.. I thought to write a follow up article on this including them :)
Appreciate the comment. I've updated the text. Thanks for the book tip as well :)
Great article, thanks! Just one thing though, factorial is not about adding numbers but multiplying them.
Thanks for that. I'll update it.. Uni was many years ago ;)
Hi Chris, just to complete the correction, you should touch also this, that appear at the end of the "Factorial" paragraph:
"I could see that this would lead to a 5 + 4 + 3 + 2 + 1 scenario."
Anyway, thanks for your great explanation, kudos!
Appreciate that, should be updated :)
Good read
dev.to/itnext/why-you-should-learn...
lol
This is really informative. Wish you could include how this recursive call is structured in memory. It helped me when I was learning about this topic. :)
Thank you for that suggestion... I will add an image showing how the calls are put on a stack and executed in what order