I've heard that running recursive code on a server can impact performance. How true is this statement, and should recursive method be used as a last resort?
+2
A:
A badly programmed recursion that does not end has a negative impact on the machine, consuming an ever-grwoing amount of resources, and threatening the stability of the whole system in the worst case.
Otherwise, recursions are a perfectly legitimate tool like loops and other constructs. They have no negative effect on performance per se.
Pekka
2010-02-15 16:54:13
Downvoted because a recursion can have a negative impact even if it does end (Consuming an unpredictable amount of memory). One that does not end is, by definition, a bug/crash.
Bill K
2010-02-15 17:17:01
+3
A:
To discuss performance you have to talk about very specific scenarios. Used appropriately recursion is fine. If you use it inappropriately you could blow the stack, or just use too much stack. This is especially true if you somehow get a recursive tailcall without ever it terminating (typically: a bug such as an attempt to walk a cyclic graph), as it won't even blow the stack (it'll just run forever, chomping CPU cycles).
But get it right (and limit the depth to sane amounts) and it is fine.
Marc Gravell
2010-02-15 16:54:24
Well, it *will* blow the stack if the compiler is not aware of recursive tailcalls to optimize it away.
kriss
2010-02-15 17:00:58
You can't really use to much stack as it's size is fixed as soon as a thread is created. Hence, you could only use to much stack by using to many threads. see http://www.odi.ch/weblog/posting.php?posting=411 for an interesting analysis
sfussenegger
2010-02-15 17:02:39
+4
A:
Recursion can potentially consume more memory than an equivalent iterative solution, because the latter can be optimized to take up only the memory it strictly needs, but recursion saves all local variables on the stack, thus taking up a bit more than strictly needed. This is only a problem in a memory-limited environment (which is not a rare situation) and for potentially very deep recursion (a few dozen recursive legs taking up a few hundred bytes each at most will not measurably impact the memory footprint of the server), so "last resort" is an overbid.
But when profiling shows you that the footprint impact is large, one optimization-refactoring you can definitely perform is recursion removal -- a popular topic since a few decades ago in the academic literature, but typically not hard to do by hand (especially if you keep all your methods, recursive or otherwise, reasonably small, as you should;-).
Alex Martelli
2010-02-15 16:57:37
Putting variables on the stack **does not consume any additional memory**. Stack size is allocated on thread creation and won't grow.
sfussenegger
2010-02-15 17:04:30
@sfussenegger: 1: (I think) the entire stack memory is not committed until needed, just reserved, which means that additional memory might need to be committed during recursion. 2. When you reach the max stack size, you get a StackOverflowException, which is even worse than running out of memory, so memory consumption can't be ignored.
erikkallen
2010-02-15 17:12:17
@sfussnegger: Basically you are right but it's not really that simple. Some languages manage their own stacks beside system stack, and at system level you can also define stacks size for threads at runtime.
kriss
2010-02-15 17:14:50
Native values will be placed on the stack (ints, longs, ...) will pointers to all the variables both local and passed in. On top of that, a stack frame itself isn't completely free--you are at least pushing the return address (I believe the VMs are coded in such a way that there are no "Registers" to push). On the other hand, there are tricks like "Tail-end recursion" that can make a recursive call operate like a loop, but this is outside my area of expertise, I just know it exists...
Bill K
2010-02-15 17:15:35
the idea is that putting variables on the stack is like putting them into an array. it doesn't take any additional memory as it is already reserved for this purpose. It's possible to run out of memory by creating threads in an endless loop and putting them asleep immediately. so stack isn't allocated dynamically. see http://www.odi.ch/weblog/posting.php?posting=411 @kriss there certainly are some factors that complicate the whole thing, but that's the basic idea. One could even argue that it takes memory as it prevents tuning of stack size.
sfussenegger
2010-02-15 17:23:54
@kriss and Bill: The JVM does not do tail call optimisation. Period. Writing recursive code in Java (or any other JVM language) on the assumption that the call will get optimised away is a recipe for blowing the stack.
Dave Kirby
2010-02-15 17:25:44
@Dave, yes -- I was answering specifically for Java (as per tags) assuming the JVM rather than some hypothetical VM with better treatment of recursion, or "other languages" as @kriss mentions in passing.
Alex Martelli
2010-02-15 17:28:22
@sfussenegger, the point is that typically the method will have more local variables than strictly needed to hold state across recursive calls; when recursing they all go into the stack frame (plus some overhead for the stack frame itself as @Bill mentions) -- when you unwind the recursion (handling your own LIFO stack, via array or other container) you can fine-tune exactly what needs to go on it (plus you can do your own "tail call optimization" even though JVM itself doesn't).
Alex Martelli
2010-02-15 17:31:49
Regardless of whether Java is capably of dynamically managing the call stack -- I don't know, that's an interesting question itself -- if you have any local variables that are objects, space will be allocated for them on the heap for each instance of the recursive function. That said, that just means that poorly-designed recursion is bad. As others have noted, you could say that of almost anything you could do on a computer.
Jay
2010-02-15 17:34:50
+4
A:
I've heard that running recursive code on a server can impact performance. How true is this statement?
It is true, it impacts the performance, in the same way creating variables, loops or executing pretty much anything else.
If the recursive code is poor or uncontrolled it will consume your system resources the same way an uncontrolled while loop.
and should recursive method be used as a last resort?
No. It may be used as a first resort, many times it would be easier to code a recursive function. Depends on your skills. But to be clear, there is nothing particularly evil with recursion.
OscarRyz
2010-02-15 16:59:31
+1
A:
Running any code on a server can impact performance. Server performance is usually going to be impacted by storage I/O before anything else, so at the level of "server performance" it's odd to see the question of general algorithm strategy talked about.
marr75
2010-02-15 17:01:23
+1
A:
Recusion is a tool of choice when you have to write algorithms. It's also much easier than iteration when you have to deal with recusive data structures like trees or graph. It's usually harmless if (as a rule of thumb) you can evaluate evaluate the recusion depth to something not too large, provided that you do not forget the end condition...
Most modern compilers are able to optimize some kinds of recursive call (replace them internally with non recursive equivalents). It's specialy easy with tail recursion, that is when the recursive call is the last instruction before returning the result.
However there is some issues specific to Java. The underlying JVM does not provide any kind of goto instruction. This set limits of what the compiler can do. If it's a tail-end recursion internal to one function it can be replaced by a simple loop internal to the function, but if the terminal call is done through another function, or if several functions recusively calls one another it become quite difficult to do when targeting JVM bytecode. SUN JVM does not support tail-call optimization, but there is plans to change that, IBM JVM does support tail-call optimization.
With some languages (functional languages like LISP or Haskell) recursion is also the only (or the more natural) way to write programs. On JVM based functional languages like Clojure or Scala the lack of tail-call optimization is a problem that leads to workarounds like trampolines in Scala.
kriss
2010-02-15 17:05:15
The JVM does not permit tail call optimisation. Clojure (a lisp for the JVM) goes through hoops to get round this.
Dave Kirby
2010-02-15 17:28:25
@Dave: I would not use the word **permit**, as far as I know, the Sun JVM does not **implement** tail-call optimization, but IBM JVM does. Also some simple cases of tail-end recursion (not all) may even be managed at the byte code generation level. The use of hoops in Clojure is merely a workaround for something that you could call a bug (or nearly so) in Sun implementation of JVM.
kriss
2010-02-15 22:41:56
A:
Deep recursion Can cause a stack overflow, which is nasty. Be careful as it s hard to get up again if you need to. Small, manageable piecs of work is easier to handle and parallize.
Thorbjørn Ravn Andersen
2010-02-15 18:48:48