Programming

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.

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.

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:

• Your maximum iteration depth is bounded and cannot overflow your machine's stack depth.
• Your algorithm can be implemented with tail-call recursion AND your language supports the same.
• Your senior/team lead wants a recursive solution.

Because in environments where none of the above are true, iterative solutions are usually more performant, safer, and better understood.

It depends on the programming language. Some languages prefer one style, others another.

IMHO almost never. Except for tree traversal, maybe.

After reading all the given responses, I'll go with the one not listed.

"When the interviewer asks you to."

I pretty much always use list/iterator combinators (map, filter, flat_map, reduce), or recursion. I guess the choice is whether it is convenient to model the problem as an iterator. I think both options are safer than for loops because you avoid mutable variables.

In nearly every case the performance difference between the strategies doesn't matter. If it does matter you can always change it once you've identified your bottlenecks through profiling. But if your language implements optimizations like tail call elimination to avoid stack build-up, or stream fusion / lazy iterators then you might not see performance benefits from a for loop anyway.

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.

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.

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.

Whenever it better expresses what you mean. In most cases it doesn't make a huge difference because the compiler don't care

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

Depends on the environment you're working in. If you're doing a lot of collaboration, it might be that you want to choose whichever of the two is more legible (almost always the loop, but perhaps the recursion). If you are in an environment where the most efficient approach is prioritised over readability, perhaps recursion would have a strong case in some circumstances.

But I think, generally, you need to answer the underlying question, not "recursion or loop". Can I improve code readability? Is this problem well suited to recursion? Am I just using recursion because it's elegant? The correct approach will reveal itsself!

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.

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.