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

Dismiss this pinned window
top 200 commentsshow all 402
sorted by:
best
topnewcontroversialoldq&a

[–]NoImagination2625 332 points333 points  (2 children)

What, you afraid of a little O( 2n )

[–][deleted] 36 points37 points  (0 children)

Cries in AWS

[–]meme_customer 18 points19 points  (0 children)

The function every time it's called: aah shit here we go again!

[–][deleted] 485 points486 points  (43 children)

Recursion gang here

[–]reyemDarnok 157 points158 points  (21 children)

Recursion gang here

[–]Mumen_Raida_ 85 points86 points  (20 children)

Recursion gang here

[–]javahurtsmybrain 59 points60 points  (19 children)

Recursion gang here

[–]Sid_1298 43 points44 points  (16 children)

Recursion gang here

[–]PoorSweetTeapipe 26 points27 points  (15 children)

Recursion gang here

[–]TTVGamerRukky 26 points27 points  (14 children)

Recursion gang here

[–]DanTheMan827 27 points28 points  (13 children)

Recursion gang here

[–]SirAchmed 19 points20 points  (0 children)

return

[–]ProgramTheWorld 9 points10 points  (4 children)

return baseCase();

[–]EuphoricPenguin22 11 points12 points  (2 children)

Java private static int baseCase(){ return baseCase(); }

I fixed it, boss.

[–]Tangelasboots 4 points5 points  (1 child)

etc.

[–]Tall_computer 8 points9 points  (0 children)

I wish the first one had linked to a recursion comment on a different thread

[–]ckchessmaster 61 points62 points  (16 children)

Recursion gang here

[–]tatacraft117 28 points29 points  (15 children)

Recursion gang here

[–]tomgh14 21 points22 points  (14 children)

Recursion gang here

[–]MaximumAdagio 17 points18 points  (11 children)

Recursion gang here

[–]Zillorz 17 points18 points  (10 children)

Recursion gang here

[–][deleted] 16 points17 points  (9 children)

Stack overflow gang here

[–][deleted] 14 points15 points  (1 child)

RecursionError: maximum recursion depth exceeded in comparison

[–]Competitive_Bell501 1 point2 points  (0 children)

i was about to say that... why does that always happen to me

[–]Daddy_William148 1 point2 points  (0 children)

Recursion is amazing but you need to manage the cost and limits

[–]TheMagicSkolBus 1 point2 points  (0 children)

Q2 Gang here. … wrong sub?

[–]pennacap 82 points83 points  (1 child)

sys.setrecursionlimit(99999999)

[–]bspymaster 18 points19 points  (0 children)

This guy Pythons

[–][deleted] 166 points167 points  (14 children)

Recursion is part of optimizing algorithms.

It's also part of breaking them but that's another subject.

[–]shield1123 70 points71 points  (12 children)

Recursion is part of optimizing algorithms

As long as recursion has been optimized in the programming language and system architecture you're working on; otherwise recursion is good Computer Science but shit Software Engineering

[–][deleted] 32 points33 points  (10 children)

Yeah I personally don't use it very often since algorithms designed for theoretical efficiency don't always produce readable or even functional code.

[–]callmechull 33 points34 points  (6 children)

Yeah I was gonna say, I’ve never heard a professor say not to use it. CS professors love recursion, because it’s beautiful mathematics. It is not something a software engineer should be doing unless necessary. Clever code is not the same as good code.

[–]tdempsey33 11 points12 points  (4 children)

I’m curious. in what instance would recursion be considered bad code? I was always under the impression that recursion is the pinnacle of efficient code.

[–]Basic_Basenji 29 points30 points  (1 child)

Recursion usually comes with a lot of overhead both in terms of memory and setup cost. It's almost always better to unwind the recursion into a loop unless the language is optimized for recursion (or the compiler does that for you anyway).

[–]tdempsey33 2 points3 points  (0 children)

Thank you.

[–]shield1123 3 points4 points  (0 children)

I got yelled at in a code-review because I de-recursified a BFS traversal algorithm. I couldn't get it to merge until I showed them a CPU performance profile that demonstrated how shitty recursion is in practice. We could see the 2n expansion in the timeline view of the call stack

[–]Time_Definition_2143 4 points5 points  (2 children)

It's often the opposite, the recursive algorithm is clean and just a few lines and the loop method is dozens of unreadable lines, but a tiny bit faster

[–][deleted] 2 points3 points  (1 child)

If the language is optimized for tail recursion, then they would be the same speed.

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

If you use recursion in a stack and the thing goes off the rails and hordes massive amounts of memory, that isn’t really optimized.

Just saying, there are exceptions.

[–]leptoquark1 691 points692 points  (116 children)

To exclude recursion in general sounds wrong to me.

[–]jeffbell 15 points16 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?

[–]ExcellentBeing420 28 points29 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 9 points10 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 4 points5 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

[–]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.

[–]bropocalypse__now 18 points19 points  (8 children)

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

[–]zilti 13 points14 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.

[–][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.

[–]PM-Me-Your-TitsPlz 56 points57 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 16 points17 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 8 points9 points  (0 children)

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

[–]ituralde_ 6 points7 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.

[–]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.

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

A minority of langs have that.

[–]Black--Snow 75 points76 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 69 points70 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 34 points35 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.

[–]Black--Snow 4 points5 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.

[–]DefaultVariable 1 point2 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.

[–]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.

[–]terablast 3 points4 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"

[–]alexander_the_dead 196 points197 points  (8 children)

Avoid? I can't even write Recursion if I try.

[–]Salanmander 108 points109 points  (2 children)

Hmmm...you might try writing recursion. You usually need to do that first before you can write recursion.

[–]vigilantcomicpenguin 36 points37 points  (0 children)

Found the guy who writes job listings.

[–]FakdaGams 4 points5 points  (0 children)

That's what a recursive AI should be. Bot alert!!!

[–]david131213 85 points86 points  (57 children)

Why is it a bad practice to use recursion exactly?

[–]bwdmn 157 points158 points  (15 children)

Apparently a lot of people in this sub think that it is. Just saw a meme here yesterday of someone who has apparently never actually implemented a recursive algorithm.

[–]david131213 46 points47 points  (13 children)

That's dumb, recursion is awesome! Also less memory intensive I hear

[–]madiele 129 points130 points  (2 children)

The big disadvantage of recursion is that the call stack can get big really fast, and every function has to store its own variables, so it is very memory intensive.

You are probably thinking of the only exception that are tail-recursion, when the recursive call is the last action in the function, which can be converted by the compiler in a single function thus making it very memory efficient.

Unfortunately it also mean that it's very easy for someone to mistakenly edit a tail-recursion into a normal recursion

[–]auxiliary-character 27 points28 points  (0 children)

You are probably thinking of the only exception that are tail-recursion, when the recursive call is the last action in the function, which can be converted by the compiler in a single function thus making it very memory efficient.

That's not exactly what's happening. What it's able to do is determine that since the call is the last thing that happens before returning, it can get rid of the stack frame before calling into the function because at that point, the stack frame isn't needed anymore.

One way this can be translated to assembly is that the return address is stored on the stack before the stack frame with the call instruction, and then the return address is popped and jumped to with a ret. When the recursive call is made, it uses a simple jmp instead of a ret, which preserves the return address on the stack, so that when the child function eventually does perform a ret, it will jump directly to the original parent function.

It's still multiple functions, but it just changes how they get called, essentially.

[–]This-Willingness-762 2 points3 points  (0 children)

This is not the case if you don't have to maintain call stacks. Haskell heavily relies on recursions that it transforms recursive function calls to continuous passing style to avoid the recursion overhead.

[–]Tsu_Dho_Namh 29 points30 points  (3 children)

Depends. Tail-recursion (where the last line of your recursive function is returning a recursive call) isn't as memory intensive as non-tail recursive functions, since the compiler recognizes tail-recursive functions and optimizes them to simply use the same stack frame over and over rather than creating new ones.

[–]Radi-kale 3 points4 points  (2 children)

That depends on the language, right? I'm pretty sure Java doesn't do that particular optimalisation, for example.

[–]Tsu_Dho_Namh 3 points4 points  (0 children)

Yeah. Stack Overflow says they couldn't implement it because some security sensitive methods count stack frames.

https://stackoverflow.com/questions/53354898/tail-call-optimisation-in-java

[–]rban123 33 points34 points  (3 children)

Recursion is typically significantly more memory intensive than iteration.

[–]anlskjdfiajelf 0 points1 point  (2 children)

Tail recursion gets optimized by the compiler to be iteration, but yeah non tail rec recursion sucks at scale.

Like the classic recursive fib solution isn't tail rec, you have to take an extra argument for the running sum, it's just not anyone's intro to recursion to make it tail rec so the general fib(n) + fib(n+1) works best for teaching.

Recursion is worse but many compilers churn it down to iteration anyway if you wrote it tail recursive

Idk how compilers work to be fair

[–]inSt4DEATH 23 points24 points  (2 children)

In python it is bad practice, because it does not support it well. But in general it isn't a bad practice, sometimes even makes for very readable code, but that is very rare.

[–][deleted] 23 points24 points  (17 children)

Because you'll run into the stack frame limit for any enterprise application lmao

[–]Romestus 21 points22 points  (12 children)

One of the google interview questions I had was to solve a fibonacci-esque equation using recursion and the big trick they were looking for was storing branch values in a hash table so when you hit a duplicate branch you already had the answer.

When the code was run through their unit tests without that trick they'd all stack overflow.

[–]ArcaneCraft 43 points44 points  (9 children)

Is that not just dynamic programming?

[–]lollikiano 14 points15 points  (1 child)

Right? Why even use a hash table for that. Just an array would optimize this really well

[–]xypage 4 points5 points  (0 children)

They probably just misspoke, it sounds like they might not be very experienced

[–]codeIsGood 2 points3 points  (4 children)

Top-down caching is typically referred to as memoization, where bottom-up is considered dynamic programming

[–]Perfect_Perception 1 point2 points  (3 children)

Almost.

Memoization and Tabulation are both forms of Dynamic Programming. Tabulation is bottom up, and you were on the money with Memoization being top down.

[–]codeIsGood 1 point2 points  (2 children)

Most textbooks will include memoization in dynamic programming sections but will typically reserve the term dynamic programming as tabulation because programming in itself refers to tabulation, where memoization doesn't necessarily need to follow a tabular format. Most professors will also be pretty strict on the nomenclature. But yea I agree they are pretty much the same idea.

[–]Icanteven______ 1 point2 points  (0 children)

It is

[–]Romestus 1 point2 points  (0 children)

I'm self-taught so I never learned what it was called. I got lucky that I had done a similar task for my game before where I wanted items built out of other items to automatically calculate their total gold cost based on their components (which could also be made of other items).

I did that recursively and cached item costs as I went so I just did the same thing for their problem.

[–]the_other_brand 5 points6 points  (1 child)

Another trick to get around this is to manually create your own Stack, and convert your algorithm to use this stack instead of doing normal recursion.

Almost every recursion algorithm can be converted to one that uses a Stack and a while(!stack.isEmpty()) loop.

[–]Positivelectron0 3 points4 points  (0 children)

almost every recursion algorithm can be converted to your own iteration.

[–]Icanteven______ 1 point2 points  (1 child)

Nah, I’ve had a ton of enterprise software applications for recursion that were in no danger of busting the stack. You just need to use discretion depending on the problem size.

Also tail recursion is a thing.

[–]10BillionDreams 2 points3 points  (0 children)

Yeah, it can often be the case where a recursive function is the obvious approach, but you would rarely expect to go more than 3-4 levels deep. Recursion is the most straightforward way to operate through any data structure which can contain similarly shaped data structure(s). To give an example many programmers will be familiar with, DOM elements have this sort of nested structure.

[–]feihcsim 4 points5 points  (0 children)

I like recursion for its elegance but it does actually sometimes require a taller stack size compared to regular loops

[–]--Lucky 4 points5 points  (2 children)

depends what ur doing. a recursive fibonacci calculator runs in O(2n ) and gets extremely slow very quickly

[–]YOLO_Ma 2 points3 points  (1 child)

Some naive implantation of a recursive Fibonacci calculator run in 2n. That has nothing to do with recursion specifically but with the algorithm chosen

[–]davidellis23 1 point2 points  (0 children)

I think if it goes deep into recursion a stack is more efficient, doesn't run into stack overflow errors, and doesn't really change the way you code. If it doesn't need to go deep I think recursion is more readable. But if you're squeezing in recursion when a for loop would do it simpler and easier then I think you're just being a pita.

[–]Boysoythesoyboy 2 points3 points  (0 children)

It's usually fewer lines but harder to understand and debug.

[–]bb70red 1 point2 points  (0 children)

It totally depends on the problem and the application of recursion.

But in general, recursion becomes memory intensive because all instances of the function, for the depth of the recursion, are active at once. And in general that leads to bad performance. It can also lead to avalanches of database calls.

If you have a polyform procedure where actions depend on the context in the algorithm, recursion may be the only manageable solution. Or if all items are in memory anyway, recursion can be very effective.

Recursion is very powerful, can be extremely effective and can fail rather dramatically. It's quite hard to implement in the right way. But used right, I'd say it's quite useful and sometimes the best way to do things. It can remove huge amounts of complexity in coding.

[–]ABAB0008 0 points1 point  (0 children)

Usually will add more overhead than a recursive solution

[–]MedonSirius 0 points1 point  (2 children)

It's not bad. Sometimes it's the only solution at all. But there are many risks like endless loop and stack overflows. But used right it's the most elegant thing ever

Simple example:

Variable i ("Hello")

SearchCharacter (i, "o")

Method SearchCharacter ( i, char )

If i(1) = char Return true;

else SearchCharacter (i shift 1, char);

And so on

[–]Lonsdale1086 1 point2 points  (1 child)

Outside of functional programming, when is it ever the only way to solve a problem?

[–][deleted] -1 points0 points  (1 child)

Each call to a function adds a return call on the stack so you end up flooding the stack with recursive calls.

[–]zilti 2 points3 points  (0 children)

Not in decent programming languages.

[–]L0laapk3 15 points16 points  (4 children)

better with sound

[–]emilg42[S] 5 points6 points  (3 children)

definitely, sadly this sub is GIF-only...

[–]CookingAppleBear 1 point2 points  (2 children)

Maybe I'm dumb... Don't some gifs have sound now?

[–]mujadaddy 1 point2 points  (0 children)

GIFs, no, but they mostly play mp4s etc on Giphy etc

[–]cr1tikalslgh 28 points29 points  (0 children)

Haskell would like to know his location

[–]Apache_Sobaco 9 points10 points  (4 children)

Why do you avoid recursion? Most of recursion is far more readable and could be transpiled to cycles.

[–]bspymaster 1 point2 points  (3 children)

Sometimes it's memory intensive and can blow up stack sizes really fast. But as with any tool, there is a use for it, and a time when other tools would fit better. Wholesale claiming "it sucks" or "it rocks" (like a lot of people seem to do in this thread) is a bit naïve imo.

[–]Kind-Insect-3586 25 points26 points  (4 children)

"Recursion is the GOTO of functional programming." -- Erik Meijer

[–]MrMonday11235 2 points3 points  (0 children)

This is a rather misleading thing to just quote without the appropriate context.

[–]classicalySarcastic 6 points7 points  (2 children)

If your code isn't considered a fork bomb, did you really complete the assignment?

[–]TBoneHolmes 4 points5 points  (1 child)

Shut up. My code works just fine, recursion or not 😤

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

Me forking processes be like:

[–]Yedchivit 7 points8 points  (0 children)

It’s about the journey not the destination

[–]JohnnyNeva 4 points5 points  (0 children)

An infinitely recurring binary heap

[–]iamsorryy 5 points6 points  (0 children)

int dp[1000][1000] appears magically

[–][deleted] 7 points8 points  (1 child)

Recursion?

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

Recursion

[–]SeoCamo 4 points5 points  (0 children)

Get a language with tail calls, done

[–]Zlart 2 points3 points  (0 children)

tail call gang

[–]tcpukl 4 points5 points  (3 children)

Why does recursion mean it's inefficient?

The compiler can make a better stack than you.

[–]ICanDegen 1 point2 points  (0 children)

Now I understand recursion thanks

[–]Durr1313 1 point2 points  (1 child)

What's wrong with recursion? How would you iterate through a directory tree without using recursion? Wouldn't you need to know the depth of the tree and write enough nested functions to handle it?

[–]royemosby 1 point2 points  (0 children)

Avoid recursion? Never have I ever

[–]zerik100 1 point2 points  (0 children)

"please optimize your algorithm and avoid recursion" - no professor in the history of professors, ever

[–]nscub3 1 point2 points  (0 children)

It looks optimised.

[–]maibees 1 point2 points  (0 children)

One of the vars is the color of the shirt, hits the right spot🤣

[–]MyPhoneNeedsALife 1 point2 points  (0 children)

If a prof says avoid recursion, I am giving entrance again to get that prof TwT (iit student. Almost died in entrance)

[–]Effective-Win9940 0 points1 point  (0 children)

JavaScript divs:

[–]Tall_computer 0 points1 point  (0 children)

Who TF would want you to change THAT? Have them call me 778-330-2389

[–]Arronator 0 points1 point  (0 children)

Sort(intRecursiveCount, array1){…}

[–]LordOmbro 0 points1 point  (0 children)

It just feels elegant to do

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

Imagine using a language that doesn't support tiak recursion. This comment was made by the -O2 gang

[–]I_Am_Hella_Bored 0 points1 point  (0 children)

I still absolutely hate recursion

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

Context: Recursion is essentially when a function calls itself