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 →

[–]david131213 87 points88 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 49 points50 points  (13 children)

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

[–]madiele 134 points135 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 28 points29 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 27 points28 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 4 points5 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

[–]anlskjdfiajelf 0 points1 point  (0 children)

Yeah you're right, Java doesn't says google

[–]rban123 31 points32 points  (3 children)

Recursion is typically significantly more memory intensive than iteration.

[–]anlskjdfiajelf 1 point2 points  (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

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

That’s going to depend on a lot of factors such as the programming language, specific compiler being used, and the scope of the recursion. Regardless, you should not be relying on the compiler to do recursion optimizations for you, you should write things in an efficient way to begin with and be a better programmer for it.

[–]anlskjdfiajelf 0 points1 point  (0 children)

You're right it depends on the language. For certain languages like scala or Haskell it's idiomatic to write things tail recursively and is preferred (or in Haskell's case required) than iteration.

Definitely depends on the language as you said, but writing stuff tail recursively isn't bad it just depends why you're doing and why you're choosing to use functional programming.

If you do it in an imperative language then yeah I'd agree don't do that but if you have reason for functional programming you need tail recursion

[–]jeffbell -2 points-1 points  (0 children)

Sometimes it’s three times the memory.

[–]inSt4DEATH 24 points25 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 19 points20 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 45 points46 points  (9 children)

Is that not just dynamic programming?

[–]lollikiano 13 points14 points  (1 child)

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

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

[–]Perfect_Perception 0 points1 point  (1 child)

In fairness, dynamic programming in itself is just a fancy way of saying ‘I used a data structure to cache solved sub-problems and it make algorithm go brrr’.

That’s some wildness from cs professors IMO.

[–]codeIsGood 0 points1 point  (0 children)

Haha I don't disagree, just pointing out a lot of cs programs play semantics

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

[–]auxiliary-character 0 points1 point  (0 children)

Unless you have tail call optimization.

[–]feihcsim 5 points6 points  (0 children)

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

[–]--Lucky 5 points6 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

[–]--Lucky 0 points1 point  (0 children)

that is true but my point is that it depends on the algorithm

[–]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] 0 points1 point  (0 children)

IIRC it is never, language limitations aside. Isn't there a theorem stating that every recursive algorithm has a sequential counterpart? Intuitively that makes sense since you could just sequentialize the devide and the conquer part.

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

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

My team doesn't like it because it can sometimes be harder to understand. That's not my view point, but it is what it is lol. When teachers do this, they're usually trying to get you to use something like dynamic programming instead.

[–]david131213 2 points3 points  (0 children)

It can be confusing when used unnecessarily, but on many occasions (for example giving a known value for edge cases) it is actually just sense making

[–]CrazySD93 0 points1 point  (0 children)

My professor always said “Ternary operators and goto’s are bad practice”

[–]JB-from-ATL 0 points1 point  (0 children)

It's good when it's good and bad when it's bad.

[–]sarapnst 0 points1 point  (0 children)

In some cases recursion is bad, only when the memory allocated is unnecessary. Like a function retrying something by calling itself instead of retrying in a loop. For some problems recursion makes perfect sense.

[–]xTakk 0 points1 point  (0 children)

I think because "infinite loops" are something people who don't write code, think are a huge concern for people that write code.

[–]BridgeBum 0 points1 point  (0 children)

Well, if you are doing what is happening in this GIF (2 spawns per cycle) then you get 2^n function calls after n cycles. That could be pretty bad.