Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!
Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.
Hope you enjoy the instance!
Rules
Follow the wormhole through a path of communities [email protected]
When you can't reasonably use a loop or when it's not particularly important for performance and the recursive function is more readable.
Honestly, in code the absolute most important quality is readability. Readability should always be prioritized until you find performance issues that matter in a specific block of code.
On a side note: not caring about performance "until you find performance issues" is a huge problem with modern software imho. That's the reason apps are so slow, updates take so long, everything uses so much space. I'd wish that performance would always be a point of consideration, not an afterthought once there are problems.
I'd rather people err on the side of readability... senior devs should know the importance of readability but still lay decent groundwork towards performance... do things the right way when it can be simple.
Junior developers should just focus on readable code. Chances are their code will be slow, indecipherable, and wrong - I'd rather they focused on fixing the indecipherablity, the wrongness, and then the speed.
But, to sort of generally undermine my own point - no rule should be an absolute in software development - sometimes premature optimization is totally justified - you just need to use common sense.
I agree that junior devs should focus on readability, rather than focusing on everything and just getting it all wrong. but as you say, if you have more experience, performance should be a point of consideration.
I think people talking about premature optimisation are often talking about micro-optimisations. Those are almost always unnecessary until you've identified choke points. Optimising the overall architecture of the code base on the other hand, is in my opinion something that should be thought about before you even start coding. That's where the major gains can often be done anyway.
I don’t think loop vs recursion choice is what significantly impacts performance in most cases. Most of the software I saw, suffer performance because of wrong API design or overall architecture. If app needs to fetch 100 objects from API which can provide only one object at the time no optimization will save that app.
App team - we need bulk API.
API team - cannot because of capacity, budget, backward compatibility, DB, 3rd patry API, not a KPI
Also it’s mostly QAs measuring performance and validating it with product guidelines which set by person who mostly detached from specific product and sometimes reality.
I think loops tend to be faster, but well done recursion might be just as fast. I just wanted to mention performance being a point of consideration when making these decisions. I 100% agree that poor (API) architecture is probably one of the biggest reasons for slow software. It's just that every bit of poor performance adds up along the way, and then we end up having fast computers (that are orders of magnitude faster than anything 15 years ago) running bloated electron apps (that are sometimes even slower than their equivalent 15 years ago) and it's just frustrating.
Just adding on that recursion could be problematic if used in the wrong way, like too many calls can over flow the call stack (assuming the compiler is not able to optimize that away).
Yeah but performance has way more to do with architecture than it does code readability. It doesn't matter how well you write your code, if it's an electron app it's going to use more ram than a native app. So I totally agree, but at the scale that it's a real problem it has more to do with architecture than the code in any given function.
Yeah but performance has way more to do with architecture than it does code readability.
Indeed, I am a bit notorious at work for speeding C++ code up by rewriting it in Python, and I have been able to do this not because my Python code is particularly fast but because the architecture of the C++ code was such a complicated and inefficient mess that it actually managed to be slower than Python.
That just hurts me. I love to bag on Python for being slow. But that also totally makes sense.
Best for what?
For performance you almost always want an iterative instead of recursive. But performance is not the only constraint.
Some algorithms are innately recursive. Forcing them into an iterative paradigm usually makes them less readable.
If you are compelled to make a recursive algorithm iterative, consider using an explicit stack. Then you can keep the structure and side step the issues related to call overhead and stack depth.
If you are compelled to make a recursive algorithm iterative, consider using an explicit stack.
yep, did that once to solve a specific problem, worked fine and if I recall correctly I could do it without making a total mess of my code
It depends on if the problem is recursive or iterative, and how much it needs to be optimized.
For example, you may use a for loop for a simple find and replace scheme for characters in a string, where you check each character one by one until you find one which matches the target, and then substitute that.
There are certainly recursive ways to do string replacement in strings which might be faster than an iterative search depending on implementation, but that's more optimization than I might need 99.9999% of the time
A recursive problem that's difficult to solve iteratively is browsing all the files in a folder and it's subfolders. Each folder may have several subfolders, which you then need to search, but then each of those folders can have subfolders. This problem can be solved fairly easily recursively but not as easily iteratively.
That's not to say it can't be solved that way, but the implementation may be easier to write
Recursive code, however, is more frequently prone to bugs which causes infinite recursion leading to crashes, as it is not a tool which is often used and requires several more fences to prevent issues. For example, in the folder example, if one were to encounter a shortcut to another folder and implement code to follow that shortcut as if it were a directory as well, then placing a shortcut to a folder within itself might cause the code to recurse infinitely without having a maximum recursion depth and or checking for previously seen folders.
I generally find that writing code that requires a lot of “accounting” is very prone to mistakes that are easier to avoid with recursion. What I mean by this is stuff where you’re tracking multiple counters and sets on each iteration. It’s very easy to produce off by one errors in these types of algos.
Recursion, once you get the hang of it, can make certain kinds of problems “trivial,” and with tail-call recursion being implemented in many languages, the related memory costs have also been somewhat mitigated.
Loops are simpler for beginners to understand, but I don’t think recursion is all that hard to learn with a bit of practice, and can really clean up some otherwise very complicated code.
My general opinion is that we are all beginners for a short part of our journey, but our aim shouldn’t be to make everything simple enough that beginners never need to advance their skills. We spend most of our careers as journeymen, and that’s the level of understanding we should be aiming for/expecting for most code. Recursion in that context is absolutely ok from a “readability/complexity” perspective.
Could your folder tree problem also be solved with a whole loop instead? I'm very new but it seems like recursion is harder but possibly more optimized approach to loops or am I incorrect here?
Any recursive algorithm can be made iterative and vise versa. It really depends on the algorithm if the function calls are a major factor in performance.
I'm exaggerating a bit there. This problem is fairly easy to implement iteratively (e.g. keep a list of unbrowsed folders and keep adding to it), but that is not the case for all problems. Some will be easier to solve in one way, though fundamentally solvable either way
Recursion is never more efficient than the best equivalent iterative solution. Recursion however allows you to solve some problems very easily and very neatly.
A naive iterative implementation would be by adding and removing the folders/files from a list.
If tail call optimization works on the (recursive) example then that's (kinda) the compiler turning a recursive function into a loop.
a whole entire loop? I'm partial to partial loops myself
When navigating a tree structure.
Processing files and folders, expression parsing, that kind of thing.
I've no idea why the factorial example is so popular, because it's one of the worst use cases for it. Still, I guess it can teach a new programmer what a stack overflow is.
I’ve no idea why the factorial example is so popular,
It is because anyone who has done anything with math (as is the case with cs students), will know how the factorial is defined in math which is also a recursive definition, so the code ends up looking almost exactly like the definition in math, and because of its simplicity, it's excellent to introduce students to the idea of recursion. So, it's a combination of familiarity and simplicity that makes it such a well known example.
Of course, in the real world you would use the implementation from a library. So whether recursion or iteration is better for factorials isn't that important of a question, since you won't be using your solution in a normal situation. The factorial example is supposed to be only used as nothing more than an example.
Came here to say this.
Generally, some algorithms are more easily expressed as recursive functions than iterative loops. ...and vice versa. And realistically, that's how you should choose ninety nine percent of the time.
But if you want to get into the weeds... Prefer iteration unless you know one or more of the following:
Because in environments where none of the above are true, iterative solutions are usually more performant, safer, and better understood.
Perfect answer.
Your algorithm can be implemented with tail-call recursion AND your language supports the same.
Just to nitpick but the compiler/interpreter needs to support tail-call recursion, not just the language. For example, tail-call recursion is part of the language spec for JavaScript (ECMAScript 6), but only certain engines actually support it (https://compat-table.github.io/compat-table/es6/ Ctrl+F tail call).
IMHO almost never. Except for tree traversal, maybe.
I would agree. Only if the performance is extremely similar but the readability (for some reason) is significantly better for the recursive solution would I choose that.
The only time I've ever really needed recursion is when I'm doing something that needs to map out some sort of tree or heavily nested object.
One example that comes to mind is when I needed a function that acts like querySelector, but also searches through shadowroots. Since querySelector does not natively search within shadowroots, I had to write a recursive function that basically starts at the root and recursively searches each node for a shadowdom, goes inside, and runs itself again.
It's definitely not the most performant solution, but it is sometimes necessary.
In Elixir & Erlang, they don’t even have a for-loop construct. You have to use recursion. And I think that’s beautiful. I also think tail-call optimization is beautiful.
Elixir does have for loops.
https://hashrocket.com/blog/posts/elixir-for-loops-go-beyond-comprehension
That being said, I have worked at a company who uses Elixir 4 years now and I have never once written one.
Oh you’re so right, I never use those so I completely forgot :X
When doing functional programming, you can't really do loops (because of referential transparency, you can't update iterators or indices). However, recursion still works.
It depends on the programming language. Some languages prefer one style, others another.
Do you have a concrete example to ask about? Are you thinking of a particular language?
Basically, do whatever is most idiomatic in your language. It also depends on what the control flow really looks like. General recursion translates to a while loop where you put stuff on a stack, and the recursive form may make more sense. Tail recursion translates to a jump or a for loop, and the loop is often more idiomatic.
After reading all the given responses, I'll go with the one not listed.
"When the interviewer asks you to."
I haven't contemplated this question before so my answer may be incomplete or incorrect, and I've also had like two double scotches, but I feel like the answer is when something is iterative, you can have a job half done and know when it is. For example adding a field to every object in a list has a definite midpoint whether you calculate it or not.
Recursion is for things that are either 100% done or not done at all. In other words until you determine all the elements, you can't and haven't done anything. For example, parsing that includes matched brackets. You can't possibly know anything until you've found the last bracket.
I've found that it's usually best to keep it iterative if it can be done with a simple data structure, like stack (DFS) or queue (BFS). But that's not always a simple task.
One common case where recursion is actually more natural is post-order tree traversals. For example if you had a tree where every node held a number and you wanted to calculate the sum of each node's descendants. This is natural with recursion because a node is able to directly sum the values returned from recursive calls. Doing this with an explicit stack would be awkward, because you don't usually get to visit a node twice (once to put children on the stack, once again to accumulate the descendants sum).
Like, just look how weird this algorithm is: https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/ I don't think I've ever done it this way.
If you switch to Scheme (or the few other tail-recursive languages), you can always use recursion, and it's the most efficient solution. It's a bit of a weird shift at first, and the hand-holding do, dotimes, loop macros will let you transition at your own pace, but soon all your "loops" will just be named-let recursion.
As a rule of thumb, I would say that recursion should never be used in place of a for loop.
If you don't know what you're doing with a recursive function then you risk pushing stuff to your call stack proportionally to the number of items you want to iterate over.
If your collection and/or the size of the stuff you're pushing to the stack is large enough, your app will crash.
If you know enough to avoid growing the call stack then you know enough to not rely on third parties to figure out if you need an iteration of recursion.
Whenever possible, you should build up a cache dynamically (approaching the desired answer step by step) instead of using recursion, which typically has no answer until it reaches the terminal state and thereby has to propagate all the way down and then propagate back up
This is only particularly relevant for recursive algorithms with multiple dependencies (I.e. our old favorite the fibonocci sequence).
That is unless you're talking about really big problems where you'd want to persist the state to disk as you go so you can resume computation if you, for instance, suffer a power outage while computing step 3,198,217 out of 3,198,218.
Whenever it better expresses what you mean. In most cases it doesn't make a huge difference because the compiler don't care
