3 ms·
This structure doesn't prevent tail-call recursion. It's a good template for most instances of recursion. To modify the GP's version, you'd just need to add an
by Jtsummers 9y ago
This structure doesn't prevent tail-call recursion. It's a good template for most instances of recursion. To modify the GP's version, you'd just need to add an accumulator parameter to the function (or to some higher scope, global or class) which could be modified and tested on each recursive call.
- tome 9y agoTechnically 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 agoNot 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 agoI disagree, because a has two recursive calls. In that case you can't make both calls to a into tail calls.
- Jtsummers 9y agoWell, 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.