5 ms·
Some years ago I had problems with recursions too, because I always had some edge cases which made my functions go wild (endless loops). But one day someone to
by JepZ 9y ago
Some years ago I had problems with recursions too, because I always had some edge cases which made my functions go wild (endless loops). But one day someone told me, that most recursive programs can be written into the skeleton below:
function a(){
if(/* Termination Condition */){
return /* Special Element */
} else {
/* Recursion: e.g. a + a */
return a() + a()
}
}
Since that day I love recursions.
- AstralStorm 9y agoThis is tree recursion that is not well optimized by modern compilers. AS opposed to tail recursion.
- Jtsummers 9y agoThis 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.
- aidenn0 9y agoIt is very rare that the tail-recursive form of a function is more readable than the non-tail recursive form. I find tail-recursion intellectually interesting, but of little use for actual programming. Contrasted with tree-recursion where the code is often so pithy that its correctness is obvious (assuming you understand recursion).
- eru 9y agoTail recursion sometimes comes up naturally. It's essentially a goto with parameters. Thus it comes up where goto is also (at least borderline) useful, eg implementing state machines.
- aidenn0 9y agoI almost added a parenthetical after "rarely" to the effect that state-machines are the one exception I've encountered.
- LyndsySimon 9y agoIf you're using a language with pattern matching (cough Haskell cough), you don't even need the conditional...
- eru 9y agoOr rather, the language recognises the conditional and makes sure you handle all the cases.
- remotebug 9y agoThank you so much for this!