0

Call stack size in JavaScript:

Three results:
- Node.js: 11034
- Firefox: 50994
- Chrome: 10402

It seems like it would be a bad idea to use recursion for things like BST insertion, because there's a chance you may be dealing with input sizes in the millions or billions.

Improve this question
3
  • 1
    I think that if you are dealing with input sizes of millions or billions, on a web page, you are going to be having all kinds of problems.
    – whatsisname
    Nov 15, 2015 at 19:26
  • 1
    Note that a recursive operation on a BST with a million nodes would only need 20ish stack levels. For a billion nodes (assuming short count, because you're not likely to find a machine that can fit a billion long-count in memory), around 30 would be adequate. Switch to an n-ary tree (eg a B+ tree) and you need less still. Most useful algorithms for handling large amounts of data are optimized for this kind of thing.
    – Jules
    Nov 16, 2015 at 11:31
  • a simple Binary Search Tree insertion can be done trivially without any recursion. And tail calls dont count as recursion
    – AK_
    Nov 17, 2015 at 19:09

3 Answers 3

Reset to default
3

Unbounded recursion is generally a bad idea if you know the recursive calls could get very deep. But if you have some way of ensuring a relatively small maximum depth for your recursive algorithm, or your language supports tail recursion and your algorithm is one that can take advantage of it, then you can safely ignore this issue.

P.S. ECMAScript 6 has tail recursion, so for Javascript at least, this will be significantly less of an issue in the future.

Improve this answer
4
  • Tail recursion only works in very specific cases, typically those where a loop would be just as readable (if not more) as recursion.
    – CodesInChaos
    Nov 15, 2015 at 21:40
  • @CodesInChaos You're right, I forgot the nuances of tail recursion. Corrected my answer to not present that as an absolute solution.
    – Ixrec
    Nov 15, 2015 at 22:31
  • 1
    @CodesInChaos: Tail recursion is not restricted to implementing a plain loop. For example, you can use it to implement a state machine using one function per state, and having transitions correspond to tail calls. So all the functions representing states are mutually recursive. IMO this solution is more concise and readable than using a loop with a big switch statement in it.
    – Giorgio
    Nov 15, 2015 at 22:42
  • ECMAScript 2015 does not have just Proper Tail Recursion, which is basically equivalent to a while loop and thus wouldn't really add much to the language, because it already has loops anyway. ECMAScript 2015 has Proper Tail Calls which are much more general and powerful.
    – Jörg W Mittag
    Nov 16, 2015 at 0:47
1

Thoughtless use of recursion can get you into trouble. However, quite often the maximum depth of recursion can be kept small. If you have recursion with one recursive call, it can often be easily replaced with iteration. If you have two or more recursive calls, usually most of the calls are doing greatly reduced work. For example in quicksort, you split an array into two parts, one is bigger, one is smaller. Do the smaller parts with recursion, and the bigger part with iteration.

Improve this answer
4
  • 1
    If you already have an iterative version, there is no point to have a recursion right next to it. It's just unnecessary code with exact same logic. Also, I believe it's possible to replace any primitive recursion with iteration, so it's not the matter of how much recursive calls you have.
    – scriptin
    Nov 15, 2015 at 20:52
  • @scriptin, that's typically how you do quicksort without any additional data structures: You start with a range [1, n] or [0, n-1]. Then you do a loop: As long as the range has more than one element, distribute the small elements to the left, the large ones to the right. Sort the smaller range with recursion, then update the range to the larger of the two ranges and back to the start of the loop.
    – gnasher729
    Nov 15, 2015 at 23:19
  • @scriptin: The general case avoiding recursion requires to build an explicit stack for the items that need doing. The method described uses recursion for its implicit stack and a loop, no explicit stack. If you can program quicksort without recursion and without an explicit stack, I'd be curious to hear how you do it.
    – gnasher729
    Nov 15, 2015 at 23:22
  • As I said, you can do that only for primitive recursion. For example, you can do that with Fibonacci numbers, which are defined with recursion, but can be implemented with loops, because in the recursion is primitive. Note there are two recursive calls in the definition of fib, that's why I'm pointing this out - it's not about the number of recursive calls. I'm sure you saw iterative implementations of Fibonacci, so you already know how I'd do that. As for non-primitive recursion, you're absolutely right - you'd need to implement a stack.
    – scriptin
    Nov 16, 2015 at 18:07
0

If by BST you mean a balanced search tree, then recursion is perfectly fine, because the balancing ensures that the recursion depth is O(log n). That's why we do it in the first place. But using recursion to implement a linked list - really bad, unless you have tail call elimination.

Improve this answer
1
  • You don't necessarily need Tail Call Elimination for iteration, Tail Recursion Elimination is enough. Tail recursion is equivalent to iteration. Tail Call Elimination would allow you to write code that can not be expressed with loops, such as state machines, which without TCE generally need some form of GOTO or labelled BREAK, but with TCE can be trivially expressed with functions for states and function calls for state transitions.
    – Jörg W Mittag
    Nov 16, 2015 at 0:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.