4 ms·
> 5. Difficulty seeing through recursion It may be a function of the code I work on but I generally avoid recursion unless I'm really sure about the bounds of
by mbell 12y ago
> 5. Difficulty seeing through recursion
It may be a function of the code I work on but I generally avoid recursion unless I'm really sure about the bounds of my input, which is rare. Few other things can take a smoothly operating service and hard crash it because the input got just a touch too big. Worse yet, there is usually no warning as the problem approaches.
Yea, some languages have tail call optimization, but I've found it to be picky even in languages that have it. i.e. an otherwise innocuous refactoring to a method to make it look a bit cleaner, but logically identical, can all of a sudden crash the process due to TCO not recognizing it anymore. This is also the type of thing that doesn't show up in testing, but shows up immediately under production load. Recursion can make some algorithms easier to follow, but I'll take a slightly more complicated algorithm over being woken in the middle of the night due to a 'stack level too deep' exception.
- nmrm2 12y agoI really want an IDE that puts a little yellow warning thingy on the screen whenever the compiler can't TCO a function.
- Zak 12y agoClojure has a form of this in that the 'recur' special form is used for tail-calls and self-calls are used otherwise. Using 'recur' from other than the tail position is a compile-time error. http://clojure.org/special_forms#Special%20Forms--%28recur%20exprs*%29 http://clojure.org/special_forms#Special%20Forms--%28recur%2...
- Elrac 12y agoAs someone who does not (yet) do recursion and looping-by-recursion in his sleep, I deeply appreciate Clojure's hand-holding to make TC situations completely explicit.
- lmm 12y agoScala has something like that (@tailrec makes it an error if the annotated function isn't TCOed), but I find TCO can make the failures worse. StackOverflowError will hit my high-level generic exception handler, retry that task appropriately and eventually fail it out using my normal failure handling. With TCO that thread instead just spins forever.
- denis1 12y agoI know scala has a @tailrec annotation which will fail to compile if the function is not tail recursive.
- nhaehnle 12y agoThere is a whole field of algorithms that are best described recursively where the recursion depth is guaranteed to be logarithmic. Sorting algorithms like merge sort are a basic example. Using recursion for those is fine. Apart from that I tend to agree with you (for the vast majority of programming contexts).
- mbell 12y ago> Sorting algorithms like merge sort are a basic example. Using recursion for those is fine. General sorting is exactly the type of thing I never use recursion for. Merge sort is O(n log n), sorting 100M records with a recursive implementation of it can blow the call stack in no time, depending on how you used recursion.
- nhaehnle 12y agoWhat exactly are you referring to? log 100M is roughly 27. A call stack depth of 27 has not been an issue on any general purpose system for a very long time now. Granted, there are certainly some niches left where you'd want to avoid that, but those are clearly exceptions.