Hacker News Reader

Comment by JepZ | Hacker News Reader

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.

View on HN

If you're using a language with pattern matching (cough Haskell cough), you don't even need the conditional...

Or rather, the language recognises the conditional and makes sure you handle all the cases.

Thank you so much for this!

This is tree recursion that is not well optimized by modern compilers. AS opposed to tail recursion.

It 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).

Tail 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.

I almost added a parenthetical after "rarely" to the effect that state-machines are the one exception I've encountered.

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.

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.

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.

I disagree, because a has two recursive calls. In that case you can't make both calls to a into tail calls.

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.

Reply on news.ycombinator.com