tail-recursion

While or Tail Recursion in F#, what to use when?

The best answer is ‘neither’. 🙂 There’s some ugliness associated with both while loops and tail recursion. While loops require mutability and effects, and though I have nothing against using these in moderation, especially when encapsulated in the context of a local function, you do sometimes feel like you’re cluttering/uglifying your program when you start … Read more

Are there problems that cannot be written using tail recursion?

Yes, actually you can take some code and convert every function call—and every return—into a tail call. What you end up with is called continuation-passing style, or CPS. For example, here’s a function containing two recursive calls: (define (count-tree t) (if (pair? t) (+ (count-tree (car t)) (count-tree (cdr t))) 1)) And here’s how it … Read more

Should I avoid tail recursion in Prolog and in general?

Short answer: Tail recursion is desirable, but don’t over-emphasize it. Your original program is as tail recursive as you can get in Prolog. But there are more important issues: Correctness and termination. In fact, many implementations are more than willing to sacrifice tail-recursiveness for other properties they consider more important. For example steadfastness. But your … Read more

Does PHP optimize tail recursion?

Here are the generated opcodes for that (sorry for the strange representation): Global ——————————————————————————- BCDCAC 0003: NOP () BCDD24 0012: SEND_VAL (CONST: “500000”) BCDD9C 0012: SEND_VAL (CONST: NULL) BCDE14 0012: DO_FCALL (CONST: “sumrand”) -> VAR 0 BCDE8C 0012: CONCAT (VAR 0, CONST: “\n”) -> TMP_VAR 1 BCDF04 0012: ECHO (TMP_VAR 1) BCDF7C 0014: RETURN (CONST: … Read more