4 ms·

Technically you can convert to a tail-call form (such as CPS) but regardless, you can't get away with consuming O(d) space where d is the depth of the tree.

• Jtsummers 9y ago
  Not necessarily. The form the OP posted is fine for most recursive calls and won't consume large amounts of memory unless the iterative equivalent would as well if you put it in tail call form: function f(n,acc) { if(n == 0) return acc; else return f(n-1,acc*n); } function fact(n) { return f(n,acc); } That's exactly the structure the OP suggested and in this case won't use O(d) space if tail-call elimination is available in the language. Now, if the accumulator is growing a list result like map or some tree traversal, sure. It'll use O(d) memory. But so will the iterative equivalent.
  • tome 9y ago
    I disagree, because a has two recursive calls. In that case you can't make both calls to a into tail calls.
    • Jtsummers 9y ago
      Well, if you're hung up on the OP's code, they do the same thing twice so we could maybe just double the result when we put it into the accumulator. If you read what I wrote I've qualified my statements properly. Not everything in the OP's form will be able to be made tail recursive. But the form they presented does not bar tail recursion and efficienct tail recursion at that. Anything that can't be made efficient recursively would likely also use gobs of memory and time if constructed iteratively.