Ask HN: Is Recursion Worth It?

> Is recursion really worth it?

It is a useful tool. Knowing how to do recursion is better than not knowing.

> My CS teacher told me to avoid recursion when possible.

Bad CS teacher. There are some algorithms that are much more elegant and easier to build in a recursive manner (i.e., walking a tree being one).

> Apparently recursion takes up more memory space than nested for loops (I'm talking about 4-5 for loops) and I lose grades for the same.

That really depends upon what local variables the recursive routine allocates. But, unless you are studying for building embedded systems with seriously constrained memory space, the difference in memory is negligible in today's typical systems with gigabytes available. And an easier to understand algorithm in recursive form would outweigh a difference in memory usage anyway.

> I lose grades for the same.

Again, bad CS teacher. Unless the problem statement explicitly indicated to not use a recursive routine, a recursive solution should be graded on whether it fulfills the rest of the problem statement requirements, not on the mere fact that it is recursive.

Well, from the perspective of a student, I think it's usually not worth doing things the way your instructor explicitly does not want them done. Sometimes you might have some overarching moral point to make, and it's worth the repercussions in your grade, but if it were me in this case, I would just avoid recursion for this class. :-)

More generally, you might look into the benefits of tail call optimization, especially in Scheme.

Recursion is great if that's the only way to "loop" in said language.

Erlang, Elixir, Haskell, APL, Prolog, etc.

I'm tempted to say you have the question backwards: loops are somewhat arbitrary; why do imperative languages need loops? Imperative/OO languages need loops because they have no other way to write iterative code. Functional languages do: recursion. Recursion is not a "feature" of functional languages, it's a natural consequence of their design. On the other hand, early imperative languages didn't support recursion at all and even modern ones support it poorly, forcing them to use something else to iterate—loops.

Recursion, by itself, does a poor job of reflecting intent. if we have a for-loop, we know that we're taking n steps or iterating over every element of a list; if we have a while loop, we know we're going until we hit some condition. Not much, but recursion doesn't even give us that.

This is where higher-order functions come in. Map, filter, fold and friends package up common recursive patterns into library functions that are easier to use than direct recursion and signal intent. When you see a map, you know that it will apply a function to every element in a list and nothing more. Moreover, when you use map, you know the iteration is going to be correct—you can't make off-by-one errors or skip elements in the list. The same idea holds for all the other higher-order functions available in functional languages' libraries, and there are a lot.

TLDR: It's worth knowing, but don't piss off your professor because you will need to pass their class.

most languages have support for tail call optimization so really this is an irrelevant question

I kind of agree with your teacher.

Some things are easier with recursion, like traversing a tree. But outside of those I'd avoid using recursion. In other words, only use recursion if you have a good reason.

Your typical code base will use very little recursion, if any.

It is generally less readable, and relatively easy to blow up your stack.

Recursion is a mathematical concept. It is so rarely used in professional software engineering that I consider it a code smell and take a very close look at it if I see it.

If your prof is trying to teach you software engineering, he or she is right to ask you to choose the simplest way to express something. If your prof was teaching you about a recursive data structure, you would be considering the tradeoffs of a recursive implementation versus another one.

What language did you write the code in?

Some languages/environments have tail call optimization. Some do not.

It depends. You can find more info from this discussion: https://news.ycombinator.com/item?id=34542559

The teachers I had were often rather dogmatic, and out of touch with the last decade of developments. I'd listen to anything they say, but take it with a grain of salt.

Recursion is something you don't use so often, but it's a useful pattern for traversing trees. It has its uses, but it can make the code a bit harder to understand.

Depends on the language. Languages like Haskell don’t have the problem and can work happily with infinite recursion due to lazy evaluation.

For most languages I use I try to avoid it though most of the time. You can get bugs because the stack gets to deep.

Recursion is sometimes very useful. A good example is traversing a file system tree. You could do the same thing with loops, but not as elegant and understandable (once you understood recursion itself, for what you need to understand recursion).

Sometimes, it's a way to elegantly solve some problems. Imagine you have a binary tree and you need to find it's depth. The answer is the maximum depth of its left and right subtree plus one. This easily translates into a recursive code.

It's true that it's rarely used in production quality code, but nonetheless it's sometimes useful and you should have a good command of writing recursive code.

Recursion is more general than loops. Even if you have tail call optimization there are thing that recursion can do and loops can't (without a supporting data structure as a stack or THE stack, but that IS recursion again). Being more general, an argument could be made for using the construct with the least power. But, as always, it depends on what are you trying to achieve and what are your constraints.

I didn't take CS, but I don't know if there's a better way to build a parser or compiler without recursion. Prior to knowing that all my code just loop over linear arrays of data, so I thought the typical Fibonacci or factorial examples were so contrived. I hope pedagogical material should at least mention where recursions are used in real world programs.

> Apparently recursion takes up more memory space than nested for loops

Recursion uses space on the call stack. The concern is not so much that you'll be using more memory, it's that the call stack has a fixed size and you might blow past that size, which will cause your program to terminate.

The comparison between recursion and "nested for loops" seems a bit off - generally it's recursion vs a single loop.

Whether it's best to avoid recursion depends on many factors. In any case, even when I do want to use iteration, it's often easiest to first formulate the algorithm as a recursive one, and then change it to use iteration.

Well is it?

It's probably a good best practice to avoid recursion when possible. In practice it often makes your code harder to reason about and/or slower to run.

Most commonly used programming languages will be slower to recurse than to loop using "for" or "while". Not all languages have tail call optimization and it can be difficult to reason about when tail call optimization is applicable.

That said, there are programming languages where recursion is literally how you loop, so it's not that it's bad so much as that these languages are in the minority.

I've run into a few cases where recursion was the only logical way to do it. For example, printing out a nested tree as a menu. It should only be used when necessary because if you don't know what you are doing, you can easily create a function that runs much longer than it should.

There are times where it's very handy, for instance drawing folder trees, or graphs.

Some dude gave me a recursion whiteboarding question one time

For a data processing command line type lightwight dev prof services type position

Lame

I didn't get it but pretended to keep a good attitude thru the ordeal

I have needed it tho for a side project -- walking a bookmark tree in Javascript

This video seems reasonable and agrees with prof

https://youtu.be/996Vu5ytEks

I do remember old xml parsers blowing up in all sorts of ways due to bugs and or malformed xml -- usually recursion-related

Which programming language support it?

Sure it works on most, but usually it is for prototyping the algo. It is really bad pratcice not separating the space of the programflow (stack) and algo's flow (heap). You will realize it when you get stackoverflow - actually this is the main reason to the forum's name.

To iterate is human; to recurse, divine.

Sometimes. Very rarely.

The main issue with recursion is not even speed, it's the fact the stack is not too large. As far as I remember, by default 2MB on Windows. You can easily keep 2GB of data in std::vector or an equivalent. And if by mistake you try to put 20TB there, most languages have decent ways to handle out of memory errors.

Still, there're rare cases when recursion is good. These are the cases when performance doesn't matter, you know for sure the depth will never exceed ~200k, but recursion helps a lot with code size and readability.