Ask HN: Is Recursion Worth It?

14 点作者 nigamanth超过 2 年前

Is recursion really worth it? My CS teacher told me to avoid recursion when possible.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.

30 条评论

weatherlight超过 2 年前

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.

评论 #34545038 未加载

pwg超过 2 年前

> 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.

评论 #34543050 未加载

评论 #34542694 未加载

评论 #34543036 未加载

marginalia_nu超过 2 年前

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.

评论 #34545904 未加载

mikebenfield超过 2 年前

> Apparently recursion takes up more memory space than nested for loopsRecursion 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.

polygot超过 2 年前

It depends. You can find more info from this discussion: <a href="https://news.ycombinator.com/item?id=34542559" rel="nofollow">https://news.ycombinator.com/item?id=34542559</a>

评论 #34580342 未加载

tjr超过 2 年前

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.

alserio超过 2 年前

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.

nicbou超过 2 年前

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.

devd00d超过 2 年前

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.

warrenm超过 2 年前

"To understand recursion, first you must understand recursion" ...so said many a professor, instructor, and developer I've known over the years (I first heard it from Dale Bryant, CS prof at HVCC[0] back in ~2000)Recursion is the perfect solution to a handful of problems (eg tree traversal)...so long as you have the memory to do it!Back in highschool, I wrote a linear (ie iterative) octree traverser in C++It was about 250 lines (not counting comments and whitespace ... printed it was about 10 pages (50 lines to the page on that old printer!)And it worked! But I did it that way because I hadn't seen recursion except as an example of solving the Fibonacci sequence (for which it is distinctly ill-prepared!)When I learned about recursion properly a few years later, I rewrote that ~250 line function down to under one page printed (with ample whitespace and comments)...it was maybe 30 lines long in its recursive formThat all said ... solving for recurrence relations is 100% "worth it" IF (and only if) the recursive runtime and/or memory usage is "too much". How "much" is "too much"? That's going to depend on the problem at hand.Linear/iterative solutions are [almost] always faster than their recursive cousins ... but they're often not nearly as intuitive------------[0] <a href="https://hvcc.edu" rel="nofollow">https://hvcc.edu</a>

pyfan878超过 2 年前

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.

cryptos超过 2 年前

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).

dTal超过 2 年前

I think it's worth distinguishing between recursion as a conceptual framework for breaking down problems, and recursion as "writing functions that call themselves in a given programming language".Recursion-the-concept is sometimes the only way to solve a problem. If you want to calculate the total number of leaves in a tree structure, the algorithm is clear: recursively sum the number of leaves in each branch. Recursion is just a way of saying "for this loop, we will need to maintain some kind of stack to track our location".Conveniently, most languages have a stack built-in in the form of a function call graph. This allows us to elegantly and concisely express recursive algorithms by simply writing functions that call themselves, exactly like the formal definition of recursion. You don't have to do it that way - you can create your own stack data structure and manually manage it, and it'll still be a recursive algorithm. But that's probably a bad idea unless you have good reason to believe that working with your language's built-in stack has limitations that are important for your use case - limited size or poor performance, perhaps.

signaru超过 2 年前

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.

code_devil超过 2 年前

It’s worth learning as an important CS concept, as it can be intuitive to express an idea and understand the algorithm on a conceptual level. Although implementing recursion can sometimes feel very confusing, apart from the fact that you might also hit a stack overflow and it runs slower than an iterative solution.In fact, a few days ago I implemented a flood fill algorithm for a drawing app I am developing. I later converted it to an iterative solution. Here’s a comparison between the two solutions<a href="https://zkpunk-xyz.vercel.app/posts/recursion_vs_iterative/" rel="nofollow">https://zkpunk-xyz.vercel.app/posts/recursion_vs_iterative/</a>

quickthrower2超过 2 年前

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.

Const-me超过 2 年前

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.

rahilb超过 2 年前

To iterate is human; to recurse, divine.

readonthegoapp超过 2 年前

Some dude gave me a recursion whiteboarding question one timeFor a data processing command line type lightwight dev prof services type positionLameI didn't get it but pretended to keep a good attitude thru the ordealI have needed it tho for a side project -- walking a bookmark tree in JavascriptThis video seems reasonable and agrees with prof<a href="https://youtu.be/996Vu5ytEks" rel="nofollow">https://youtu.be/996Vu5ytEks</a>I do remember old xml parsers blowing up in all sorts of ways due to bugs and or malformed xml -- usually recursion-related

azatom超过 2 年前

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.

评论 #34545947 未加载

cypress66超过 2 年前

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.

tapotatonumber9超过 2 年前

It’s discussed in depth here: <a href="https://news.ycombinator.com/item?id=34542559" rel="nofollow">https://news.ycombinator.com/item?id=34542559</a>

MathMonkeyMan超过 2 年前

Writing a recursive descent parser with nested for loops would sure be a pain.

jeffrallen超过 2 年前

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.

aynyc超过 2 年前

For those who have written commercial code for tree like traversal, did you use recursion or iterative approach?

cpach超过 2 年前

What language did you write the code in?Some languages/environments have tail call optimization. Some do not.

stuaxo超过 2 年前

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

nailer超过 2 年前

Well is it?

评论 #34544227 未加载

arthurcolle超过 2 年前

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

magic_man超过 2 年前

Probably just use stack and a loop. Recursion has more overhead.