Given a choice, would you choose an iterative approach or a recursive one?





17 votes · Closed

It's beautiful how the same problem can be solved using an iterative or a recursive algorithm, both having their own advantages and disadvantages. Personally, I first got familiarized with looping structures and was fairly comfortable thinking that way (I imagine it's the same for most of us back when we started). My first encounter with recursion was a scary one (I was specifically made to fear it) and it took me a couple of years to actually try it myself and get comfortable with the concept and then it did not take much time to fascinate me.

Having watched quite a lot of lectures from SICP on YouTube a few years back (still did not get through the entire list), and having used them in most of my implementations at work and in my personal projects, I still like recursive algorithms. Furthermore, concepts like tail recursion make it even interesting.

However, I read an awesome post recently and it talked about so many disadvantages of using recursion, most of which I do agree with myself. There were a few comments about that recursive vs iterative thing, but I just wanted to ask to the community, for if you had a choice, what would you rather go with: an iterative approach that is easier to understand (as most of our minds are trained that way) or a recursive approach (that feels very functional)?

Learn Something New Everyday,
Connect With The Best Developers!

& 500k+ others use Hashnode actively.

Hipkiss's photo

I think i'd go with iterative, not because it's better or anything like that but purely because it's easier to understand by other developers who might be on my team now or in the future.

But it also depends on the problem. For example iterating through the DOM (deconstructing or constructing) requires recursion in order to access the nth set of children and their attributes. Thinking about it, I guess a purely iterative approach could be used but it would be overly complicated and the code would be needlessly long when compared with the recursive method.

So whilst it's important to consider the technical procs/cons of each I would suggest that the most important is what the team are most comfortable with as well as what the problem requires in order to present an effective solution.

Mark's photo

Some of the rules are silly to apply outside of the context where they were invented. For example

Avoid heap memory allocation

That makes sense if you need extreme reliability, have serious hardware constraints and ten times the budget other organizations have.

But if you're just creating a webpage or data analysis script or even for 95% of server code (usually performance is determined by 5%), you're just going to spend a lot of extra time to save the computer some seconds.

I'm also not convinced that recursion is inherently complicated, I think it has more to do with what we're used to. I've also seen some needlessly complicated code to traverse trees, written by people scared of recursion.

j's photo

stuff ;)


Sébastien Portebois's photo

To add more about

Avoid heap memory allocation

It also helps to know your language/compiler: if it supports tail call optimization, then you can do recursive call and avoid the memory footprint you would usually get from many recursive calls

Amrit Pandey's photo

I consider myself an algorithm/data-structure rookie. But from the places where I have used recursion over iteration I can say that its purpose is always to reduce code length. The sole purpose for me to use a recursive function is to make program efficient and code cleaner. It has its dis-advantages, I agree.

Now coming to iteration vs recursion, it would have been great if it were up to us to elect one. Becuase if you see, javascript engines are optimised to run iteration efficiently over recursion. So its faster to use a for loop than recursion. This is not the case with other programming languages. But as I use javascript heavily, it is a matter of concern for me.

In languages like C and C++, the program's efficency is directly proportional to the code complexity. So you may write easy to read code and there will always be room to improve it through methods like recursion.

Mike Schinkel's photo

That post is interesting, and mostly good. But if you read the comments many people who replied point out that the author was overzealous with their dismissal of recursion.

Ironically, one of the authors other claims is to not use the heap yes an iterative algorithm is more likely to use the heap than a recursive one because you have to keep track of that state somewhere.

So, use recursion when the data structure is recursive, such as an HTML DOM or a directory structure or object graph. If you are worried about infinite recursion pass in a depth variable and increment it each level, test for a max number of levels and fail gracefully if it uses too many levels.

P.S. Who was it that specifically made you fear recursion? Maybe we need to give that person some mob justice? #onlykidding

Marco Alka's photo

First of all, it's important to know what kind of problem you have. Most of the time, things like memory constraints and execution time don't even matter, so you should focus on what you can type quickly and feel comfortable doing. Everything else is premature optimization and will kill your capacity and burn through your project's money.

If you, however, know that whatever you are writing might have a big impact, because it will iterate infinitely (or at least a lot of times), it's important to know your compiler/interpreter. Because if they don't do things like tail call optimization, you will run into a stack overflow easily. Many modern languages support this feature, but you should be careful and make sure anyway.

haael's photo

grinding cryptography

Recursive. It's more natural, functional-style, easier to debug and closer to mathematical definition. Iterative would be better for some infinite structures like streams.

Want to read more?

Browse featured discussions

© 2020 · Hashnode