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? Actua...
For further actions, you may consider blocking this person and/or reporting abuse
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