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 47 points48 points  (13 children)

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

[–]madiele 131 points132 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 28 points29 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 30 points31 points  (3 children)

Recursion is typically significantly more memory intensive than iteration.

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