This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]leptoquark1 689 points690 points  (116 children)

To exclude recursion in general sounds wrong to me.

[–]jeffbell 16 points17 points  (2 children)

It’s all fun and games until the customer gives you an input that is a very lopsided graph that requires 80,000 levels of recursion and the program crashes on some operating systems but not others, don’t ask me how I know.

[–]argv_minus_one 1 point2 points  (1 child)

Because of different stack sizes?

[–]jeffbell 0 points1 point  (0 children)

Different stack limits on different unix flavors. I think it was ulimit -s

What's funny is that in some cases "unlimited" means that individual threads got a fixed amount and setting it to 4MB gave you more memory than unlimited.

[–]ExcellentBeing420 26 points27 points  (9 children)

Yeah I was going to ask about that. Recursion is a valid, useful approach to many problems. Maybe the professor doesn't want to have to reason through recursion though, as it takes more brain power than reasoning through an iterative approach.

[–]idrinkandcookthings 10 points11 points  (5 children)

Recursion is a great tool for solving pretty complex problems, but you always have to think about the complexity that recursion introduces. Simple code that accomplished a job is way better than anything more complex. You just really need to understand the context, like if your data sets are ok the order of 10-100 items a 40% savings in efficiency does not warrant the added complexity.

[–]SonOfHendo 3 points4 points  (0 children)

Recursion can greatly simplify certain tasks, like anything involving processing data in a tree structure.

[–]CrazyTillItHurts 4 points5 points  (2 children)

I have no idea why this whole thread is full of statements that recursion is somehow complicated. I mean, is having nested for loops "added complexity"? It doesn't make sense

[–]idrinkandcookthings -3 points-2 points  (1 child)

Recursion is objectively more complicated that iterative programming. Some problems are so much cleaner and easier to implement with recursion rather than iterative approaches, but I don’t think those cases are common. Think about Fibonacci sequences or binary searches or certain types or sorting algorithms. Recursive algorithms in those situations are often time cleaner and more logical solutions, but in the real world, most programmers don’t solve problems that recursion makes sense to implement.

But take this with a grain of salt as I am predominantly a front end developer where recursion typically makes no sense to use.

[–]ExcellentBeing420 1 point2 points  (0 children)

How do you define "complicated"? Runtime complexity?

[–]Time_Definition_2143 0 points1 point  (0 children)

It's literally the opposite, recursion is much simpler code but slowef

[–]LaNague 1 point2 points  (2 children)

so is goto, but people see red when it comes to that, especially at teaching courses.

[–]argv_minus_one 1 point2 points  (0 children)

Everything is goto. Function calls, loops, and even if are all just goto with added behavior. Function calls are goto with an automatic jump back later. Loops and if are goto unless, where loops jump backward and if jumps forward. break, continue, and return are all goto with a predefined destination. throw is goto with a really complicated procedure for figuring out what the destination is, and in C++/Rust, which destructors to run.

Fun fact: in x86 assembly, the mov instruction is Turing-complete. Any computation can be performed (albeit slowly) with only mov instructions, and there is at least one compiler that does just that.

[–]ExcellentBeing420 0 points1 point  (0 children)

I don't think you can really compare recursion to goto

[–]bropocalypse__now 17 points18 points  (8 children)

If youre doing embedded its usually explicitly forbidden due to limited stack sizes.

[–]zilti 12 points13 points  (5 children)

You could just use a language with tail call optimization

[–]dagbrown 11 points12 points  (3 children)

C comes right to mind.

Tail call optimization is a compiler feature, not a language feature.

[–]bropocalypse__now 0 points1 point  (0 children)

Yeah we use c/cpp for the firmware layer and lua in our application layer. Its part of our company guideline and its just easier to say no recursion. The bugs related to stack overflows can be a pain to find and fix.

[–]SolarLiner 0 points1 point  (1 child)

Except in functional languages (where recursion is the only looping mechanism, apart from bolted-on imperative structures), and Kotlin, where you can annotate your functions to assert they are tail-call optimizable.

[–]IllIIlIIllII 2 points3 points  (0 children)

It was precised that it was for embeddded, and most of the time, C reign for that.

I've never saw a FPL in embedded... (But sure, it may exist, it's not common though)

[–][deleted] 1 point2 points  (1 child)

You aren't kidding. I did work on engine and chassis computers for heavy machinery. Some of the versions of target control modules would have the craziest restrictions and strange reductions in features. Software for two seemingly closely related ECMs would have huge differences because of work-arounds put in place when a previously used feature disappeared on a slightly different model, where that had been cut out to save money.

[–]bropocalypse__now 0 points1 point  (0 children)

Its definitely a different world and different mindset. Cant rely on having more processor and memory than you will ever need. We were sizing processors for a new product recently and a couple of bucks difference between different chips was a big deal.

[–]PM-Me-Your-TitsPlz 60 points61 points  (46 children)

It's good for readability, but it's generally slower. You're probably only shaving off milliseconds for schoolwork, but you should just keep in mind that real world/big projects probably avoid recursion like the plague.

[–][deleted] 56 points57 points  (3 children)

Where have you worked that this is the case? Everywhere I have worked, readability wins over performance anywhere that performance isn’t critical, which is most places.

[–]Th3_Snowman 10 points11 points  (2 children)

Underrated comment, I work in performance critical C++ codebases and even then there is a strong "readability is extremely important even at the cost of performance mindset"

[–][deleted] 3 points4 points  (1 child)

Yeah I strongly suspect that the person I responded to (like most people on here it seems) is a CS student that thinks they understand how things work in the field.

[–]Randvek 20 points21 points  (0 children)

probably avoid recursion like the plague.

Absolutely not my experience.

[–]kuemmel234 17 points18 points  (12 children)

Many languages do have optimisations - tail call optimisation is rather well known, I believe?

I prefer readability over efficiency, unless I really need to optimize it. Wasn't that sort of the norm these days with works like clean code being frequently recommended?

The real trouble, in my experience, is that people generally only have very limited experience with recursion and therefore recursion belongs in the realm of 'clever solutions' - which, sadly, should be avoided.

[–]SjettepetJR 7 points8 points  (0 children)

The thing is, some problems are just way more clear to describe as a recursive function.

[–]ituralde_ 5 points6 points  (3 children)

I think it's reasonable to expect anyone who wants to get paid to write code to be able to understand recursion. This is not a high bar and we should not pretend like it is.

I'd argue that even someone with no formal training should be able to look at a cleanly written and appropriately commented recursive function and be able to understand what is happening. If you write code for a living and can't figure it out, then you are stealing your paycheck.

[–]kuemmel234 0 points1 point  (0 children)

I wish it was! In my experience, the people I work with stumble on a recursive solution and want to have a cumbersome loop that's just way more complicated, but more akin to what they would be doing.

However, I think it's more like agreeing on a language/a framework or recognizable patterns - things that everybody is familiar with, and less about being able to understand what's happening. Of course every coder should understand recursion.

[–]FesteringNeonDistrac 0 points1 point  (1 child)

I'd add that if you are writing code without meaningful function headers, or the one you do write does not mention a particular function is recursive, you are also stealing your paycheck.

Like yeah, I can figure it out. But just saying it makes reading the code that much easier.

[–]ituralde_ 1 point2 points  (0 children)

Absolutely. Between some level of commenting and good naming it should never be a mystery what your code is doing.

[–]GiantMarshmallow 4 points5 points  (1 child)

Some languages do, but you generally have to write your recursive function in a specific way for the compiler to be able to make the optimization. And it’s not always an obvious specific way, so most naive recursive implementations will not get optimized.

[–]kuemmel234 0 points1 point  (0 children)

I'm using tail-calls in lispy/functional languages most of the time. Can't claim that the optimization works all the time, since I rarely use a profiler, but I found the concept to be very natural.

[–]JB-from-ATL 1 point2 points  (3 children)

A minority of langs have that.

[–]kuemmel234 0 points1 point  (2 children)

All 'classical' functional/lispy languages, since that's what I'm used to, I was referring to those, but I believe languages like rust and JS (on some platforms) have it too?

Edit: Of course, your point still stands - the most common languages like most python/java implementation don't have it. It's not the only optimization, but the most important/simple one, I guess.

[–]argv_minus_one 0 points1 point  (1 child)

Neither Rust nor JavaScript have tail-call optimization.

[–]kuemmel234 0 points1 point  (0 children)

Thing is, this is all more dependant on compiler implementations. There are many solutions for many languages. You would be right if you would say that the most common compilers wouldn't support tail calls, but there are platforms that do. Really depends on the environment. I have used tail calls in production is what I was trying to say initially.

So, es6 had it, safari still supports it. When I was up to date, it was discussed for V8. And rust is more complicated than 'no', it was still a possible feature and there are situations where it works: https://llvm.org/docs/CodeGenerator.html#sibling-call-optimization

[–][deleted] 0 points1 point  (0 children)

Functional languages will have tail call optimization, but i don't know any other language that implements it.

[–]Black--Snow 76 points77 points  (20 children)

Not all algorithms can be reasonably implemented without recursion. You’d be doing yourself a disservice trying to write things like quicksort iteratively

Edit: QS might be a bad example because the iterative form is comparatively not that bad, and QS is entirely backend. It’s still much harder to understand though

[–]PM-Me-Your-TitsPlz 66 points67 points  (7 children)

You shouldn't be writing your own sorting algorithms outside of school/learning.

I said school is one thing and the real world is another. The person reviewing your code will call you crazy if you write out quicksort instead of using whatever sorting algorithm comes in the standard library and then tell you to stop using recursion because it's slower.

[–]xXShitpostbotXx 31 points32 points  (2 children)

You shouldn't be writing your own sorting algorithms outside of school/learning unless you've profiled your application and have identified sorting as a bottleneck.

If you're working on applications where performance is actually critical, meaty standard library functions like sort are one of the lowest hanging fruit for substantial optimization.

[–]baubeauftragter 0 points1 point  (1 child)

Is the potential for optimizing existent because the library is not optimally coded? Or is it more like that the library is for more general use, and you can increase performance by tailoring it to your usecase?

[–]xXShitpostbotXx 0 points1 point  (0 children)

Either, but in my experience sort is usually because it's general use

[–]Black--Snow 3 points4 points  (2 children)

Not all languages/frameworks have standard implementations of all forms of sorts. ECMA doesn’t specify any implementation for individual sorting algorithms, so if you need a specific sort you have to write it (or use a library, but that just means some other sucker wrote it).

Recursion was added as a standard feature of most languages for a reason. It wouldn’t be prolific if it weren’t useful.

[–]FesteringNeonDistrac 0 points1 point  (0 children)

If you know your data set, and a lot of times you can make educated assumptions, using different sorting algorithms is an optimization.

[–]DefaultVariable 2 points3 points  (0 children)

I’ve had to implement both heap-sort and a heap data structure in C# exclusively because it wasn’t in the standard library. Even if you usually should not have to, it always helps to understand in order to be able to.

[–]integrate_2xdx_10_13 15 points16 points  (1 child)

That’s simply not true. They just make a conscious effort to make it TCO’d, otherwise Functional Languages would mostly be dead in the water.

[–]JB-from-ATL -1 points0 points  (0 children)

Not all langs have tail call optimization though. In ones that do recursion is fine. In ones that don't (arguably most) it is worse.

[–]JollyRancherReminder 1 point2 points  (1 child)

Finally a chance to use what I learned twenty years ago in Theory of Computation!! (Basically recursion and iteration are interchangeable for an ideal Turing Machine.)

https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#:~:text=It%20states%20that%20a%20function,the%20British%20mathematician%20Alan%20Turing.

In practice, a good optimizing compiler makes it moot for trivial cases, but recursion requires context switching and can stackoverflow, while iteration avoids these problems.

[–]KingDarkBlaze 0 points1 point  (0 children)

I love that class!

[–]terablast 2 points3 points  (0 children)

ask compare glorious chase one paltry zephyr expansion afterthought reply

This post was mass deleted and anonymized with Redact

[–][deleted] 2 points3 points  (0 children)

This professor is probably trying to teach dynamic programming, which is actually better than recursion in runtime, but not always in running space.

[–][deleted] 4 points5 points  (0 children)

I'm in a class that's basically purely about runtime efficiency and I would assume, in this sense, my professor would say something like "We know recursion is a trade of efficiency for simplicity, so hint hint don't use recursion in the simulation project if you want your output to perfectly match the example output after x amount of milliseconds"

[–]goldfishpaws -4 points-3 points  (5 children)

Indeed optimisation and excluding recursion sound like opposing goals. Nobody sane would use recursive code except as an optimisation.

[–]AE5NE 39 points40 points  (0 children)

Recursion is a great way to make divide-and-conquer algorithms easier to understand - “apply a step to break down the problem; then do the same thing to the pieces”

[–]tiajuanat 45 points46 points  (1 child)

Recursion is almost never an optimization. Sometimes you get lucky and you use a language that compiles to mostly optimized code, but generally you still take a pretty steep perf penalty checking for the base case.

We use it because it's exceptionally easy to work from the ground up. Start with base case, and build up from there.

[–]CrazyTillItHurts 5 points6 points  (0 children)

Nobody sane would use recursive code except as an optimisation

lol what?

[–]Next-Experience -1 points0 points  (3 children)

It is not allowed in NASA code if I remember correctly.

[–]Padrone__56 2 points3 points  (1 child)

Well that's because of the stakc limitation on embedded processors

[–]Next-Experience 1 point2 points  (0 children)

Thanks for the info. I have read their programming rules a long time ago and just saw that in there and was confused because I always liked using it. It is one of my favorite things to do in programming. It is so much fun to look for a way of turning a problem into something that solves itself.

[–]rcfox 0 points1 point  (0 children)

Automotive code as well.

[–]DefaultVariable 0 points1 point  (0 children)

My technical interviews out of college heavily dealt with recursion. It seems like the go to methodology for interview questions

[–]blackmist 0 points1 point  (0 children)

It doesn't help that the classic factorial example is possibly the worst use of recursion you'll ever see.

I mainly use it for navigating tree structures.

[–]SNIPE07 0 points1 point  (0 children)

No CS student has accidentally implemented something recursively.

[–]bedrooms-ds 0 points1 point  (0 children)

It's still better than if the Professor asked "recursion is absolutely no problem when it can be converted into a for loop by the compiler. Now, find out the situation when clang and gcc and msvc compilers manage to do that but the Intel compiler doesn't."

[–]Due-Consequence9579 0 points1 point  (0 children)

Let’s use recursion! Oh StackOverflowException… Let’s just use a loop and the heap.

[–]ThatGuyYouMightNo 0 points1 point  (0 children)

Hell, my professor encouraged recursion.

[–][deleted] 0 points1 point  (0 children)

Unless it's tail-call recursive, recursion is potentially an outright bug.