7 ms·

This Function is Not Tail Recursive

25 points by fogus 16y ago

quanticle 16y ago
It seems like a difference without distinction to me. I mean, sure, it doesn't fit the precise dictionary definition of tail recursion, but the function would be fairly trivial to implement in a purely tail recursive manner. As such, its close enough for most purposes.
- kylec 16y ago
  It matters when you have an interpreter/compiler that does tail-call optimization. If the function is tail recursive then the recursion will only use O(1) stack space, while non-tail recursive functions will use O(n).
- bitwize 16y ago
  Tail recursion means that there's nothing in the continuation of the recursive call besides a return from the outer call. This means that a compiler can optimize away the saving of a new stack frame for a recursive call, because the old stack frame of the enclosing call will never be used again. That's tail-call optimization. If there's stuff in between the return from the recursive call and the return from the enclosing call (like the multiply in this factorial example) then the old stack frame will have to be kept around which means you must use unoptimized recursive calls.
- DrJokepu 16y ago
  Sometimes it's trivial, sometimes it's not. Sometimes it's not even possible (e.g. the naive Fibionacci algorithm). Sometimes all you need to do is to add an accumulator argument to the recursive function. Still, it's not something that can be easily automated and I'm yet to see a compiler that does it automatically. In computer science (and generally, in mathematics), every word of the dictionary definition matter.
- deleted 16y ago
  [deleted]
- ori_b 16y ago
  It makes all the difference in the world - One can be converted by the compiler into a loop that will never use more than one function call's worth of stack, and the other must cause an unbounded amount of memory usage dependent on the input argument. In other words, it's the difference between O(n) and O(1) memory usage.
- michaelcampbell 16y ago
  > As such, its close enough for most purposes. Well, this purpose was to make it a tail call so that it could be optimized. Since it either is or it isn't, "close enough" to "is" is, sadly, "isn't". Which turns it from O(1) to O(n).
j_baker 16y ago
On the JVM, wouldn't * be an operator rather than a function? Would it even make a difference?
- DrJokepu 16y ago
  No. The very last instruction of tail recursion (on the recursive branch, not the base case of course) should be directly returning the return value of the recursively called function. Otherwise, you cannot overwrite the stack frame (in other words, you need to remember the values of temporary variables of previous iterations).
- Hemospectrum 16y ago
  At the assembly/bytecode level, you still have to save the return value of the recursive call and then do something to it, whereas a tail call wouldn't need to save any intermediate value because it would immediately return it as soon as it got it. I guess Java's infix notation kind of obscures this. This is one of the reasons why functional programmers prefer to consider everything a function. It's also why some languages (like Clojure) have special syntax for tail calls, with special error messages if you goof up the semantics.
  - Uchikoma 16y ago
    I like this idea - never came up to me before n * fac(n-1) vs. * n fac(- n 1) or * (n, fac(n-1)) as a method call, which makes it clear * is the last function that's called.
  - eru 16y ago
    Yes, in Lisp there's no real difference between * or car. In Haskell, which has more syntax, you can use * in infix notation, but so you can with other function. E.g. the function `on`. Quoting from the documentation: on :: (b -> b -> c) -> (a -> b) -> a -> a -> c (*) `on` f = \x y -> f x * f y. Typical usage: Data.List.sortBy (compare `on` fst).
- CodeMage 16y ago
  It wouldn't, because you would still have to do something else after the recursive call to your function. That would prevent you from applying tail-call optimization, which is the point behind making your function tail-recursive in the first place. For those who aren't familiar with tail-call optimization, here's a very simplified explanation: if the very last thing you do in a function is call it recursively, then instead of allocating the space for its local variables (and any other local state it might have) for another call, you can simply set the arguments to their new values, reset the local state and do an equivalent of "goto" to the beginning of the function.
deleted 16y ago
[deleted]
kenjackson 16y ago
One way that would make that particular example clearer is to convert the multiplication from an infix operation to a function call: return n == 0 ? 1 : n * fac(n -1); becomes return n == 0 ? 1 : multiply(n, fac(n -1); This makes it a fair bit clearer, IMO.
- deleted 16y ago
  [deleted]
  - kenjackson 16y ago
    [no longer applies to the comment]
- barrkel 16y ago
  I suspect a better approach is to make expected tail recursion a language feature, and have the compiler emit an error if the returned expression is not in fact valid for a tail call. Imagine if it were 'treturn' or something. It's not something that bites people who have been around this mulberry bush before, but I think it can very likely catch problems that novices have, thinking they're writing an O(1) space solution but actually using O(n) stack.
  - eru 16y ago
    OK. But then, even if somebody is using `return', and its tail-recursive, it should be optimized. (`return' should just not raise an error, if it's not tail-recursice.)
Roboprog 16y ago
A comment on the site itself noted that tail recursion does not imply parallelization -- in fact, I would make a stronger statement that it forces serial execution, at least as far as funneling results of one "iteration" into the next. The benefit, as "everybody" here of course already knows, is to reduce memory (call stack) usage. Knowing how to implement tail recursion allows you to write in an "assign only once" type of language, without blowing up the stack. And using such "invariant symbols" in a routine allows the compiler/interpreter to seek parallelization at other points in the function on your behalf. OK, so I just contradicted myself, but the point is there is an rather indirect connection between tail recursion and parallelization.
sedachv 16y ago
No one addressed the parallelization claim, so here goes: The ability to parallelize purely functional code comes from the Church-Rosser theorem (http://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem http://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem), which states that you can do beta reductions in any order in the lambda calculus and get the same term. The thing with tail-recursive code is precisely that there is only one way to do a reduction - the function has to call itself at the end. That's what makes tail-recursive code "iterative." As soon as you introduce multiple reduction paths, you need a stack for the intermediate results - think of for example a recursive divide-and-conquer algorithm. This Kornelius Fuhrer dude shouldn't be writing articles on parallel programming, he should be reading books about it.
- barrkel 16y ago
  I can, however, see a compiler turning simple cases of tail recursion into recurrence relations, and re-extracting the loop, but it's a relatively long way to go to get back that iterative bit of the problem, especially as a language in which tail recursion is often used probably won't be working with mutable arrays as often - a loop over input and output arrays being probably the easiest parallelization candidate.
  - sedachv 16y ago
    I never thought about it that way. That's quite clever and out of the box! Guy Steele gave a very good talk about the problem (basically, "tail recursion considered harmful") and solution ("divide and conquer") at ICFP last year: http://docs.google.com/viewer?a=v&q=cache:bBDVKW8DP6UJ:labs.oracle.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf+foldr+considered+harmful&hl=en&gl=ca&pid=bl&srcid=ADGEESiHWEmfK12_eOyYM0465fA2ltUZLfPwQxtlNADEVwhJgdiIFKB1_YRvSv064kacRgLtLX7CWHrBBi72WaPrlXcrQqRXaqJB6-DSA10Sej9jFkXJM7GVPVx-VUfkmho-s5sduHga&sig=AHIEtbTLZ4NCoMphAYt6CkQ7PuspHJqNCw http://docs.google.com/viewer?a=v&q=cache:bBDVKW8DP6UJ:l... APL-style operators (map/reduce, paralations, NESL, etc.) are definitely the way to go. Not only do you get parallelization "for free," but optimizations like map fusion (see http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance http://www.randomhacks.net/articles/2007/02/10/map-fusion-an..., and Rich Waters' earlier work on SERIES: http://series.sourceforge.net/ http://series.sourceforge.net/) become easy - something like that is almost impossible to do with loop analysis. All that, and you end up with clearer, shorter code. Due to all these reasons, I'm convinced that automatic loop parallelization is the biggest waste of time in parallel computing research.
sophacles 16y ago
In the example case, and many others, the tail-recursive version is the simple application of an accumulator. So for the factorial example, an accumulator version would be (in haskell since I don't know the example language very well): fac1 0 = 1 fac1 n = (*) n (fac1 ((-) n 1)) -- tail-recursive fac2 0 acc = acc fac2 n acc = fac2 ((-)n 1) ((*) acc n) To me, something in with a pattern of: f v = g v (f (t v)) where f, g and t are functions (t is a transform on a, in the factorial case it is (-), Can usually be turned into the form (mechanically even): f v acc = f (t v) (g v acc) Does this hold for all cases or am i missing something? If it does hold, could a language just implement the TCO for it, and therefore couldn't we just consider the very first implementation of fac1 to be tail-recursive? edit: It is ugly but changed my exmple code to match the pattern i describe exactly.
- Psyonic 16y ago
  I believe this has some issues if the operation isn't commutative. For example: blah 0 = [] blah n = (++) [n] (blah ((-) n 1)) -- blah 5 -> [5,4,3,2,1] blah2 0 acc = acc blah2 n acc = blah2 ((-) n 1) ((++) [n] acc) -- blah2 5 [] -> [1,2,3,4,5] If we changed the tail to: blah2 (n-1) ((++) acc [n]) it would work in this case, but then we've flipped the arguments, and I have a feeling we could come up with a function where simply flipping the arguments won't work, though I can't think of one at the moment.
  - sophacles 16y ago
    Good point! It becomes hard to do mechanical transforms like I suggested when you have to keep track of properties like this for every function. Thanks!
    - Psyonic 16y ago
      Ya that's the problem. Here's what I originally intended to write, but couldn't think of how to do cons in haskell so I used list addition. With cons (:), you can't rewrite it with the arguments swapped, so no simple mechanical transform will be able to fix this. blah 0 = [] blah n = (:) n (blah ((-) n 1)) -- blah 5 -> [5,4,3,2,1] blah2 0 acc = acc blah2 n acc = blah2 ((-) n 1) ((:) n acc) -- blah2 5 [] -> [1,2,3,4,5]
geuis 16y ago
I don't understand what his last statement means: "So please, do not call all functions where the last function call in your source code is a call to itself, tail recursive. A function is tail recursive, if the last operation is a function call to itself." It reads to me as "Don't call functions that call themselves last tail recursive. A function is tail recursive if it calls itself last." That's saying the same thing, if my reading of it is right. His oddly-placed commas don't help.
- Jtsummers 16y ago
  I can't read the article (silly work web filters), but if you're quoting him correctly then I have an idea. ( function foo(n) { ... return n+foo(n-1); } is not tail recursive because the last operation is not the recursive function call, but rather the addition. function bar(n,acc) { ... return bar(n-1,acc+n); } is tail recursive because the last operation is now the recursive function call.
- akeefer 16y ago
  He's pointing out that the order of statements in the source code doesn't necessary correspond to the order of evaluation. In this case even though the function call is the last statement in the source code, it's actually an argument to the multiplication, and the multiplication is the last operation being executed. That's non-obvious when just looking at the code, since the function call looks like it's last.
btilly 16y ago
The correction is incorrect. A function is tail recursive when the last thing it does is call some function, possibly different. Yes, you can have a mess of different functions that are mutually tail recursive. For an example of how this comes up, think "state machines" with each call being another state transition.
- raganwald 16y ago
  I am used to the term Tail Call for a function that returns the result of calling another function. Tail Recursion is then a special case where a function makes a Tail Call to itself. Mutual Tail Recursion is another special case where multiple functions make tail calls to each other in such a way that a function will end up calling itself indirectly. Not a tail call: var even = function (x) { return x == 0 || !even(x-1); } Mutually Tail Recursive: var even = function (x) { return x == 0 || odd(x-1); } var odd = function (x) { return x == 1 || even(x-1); }
  - eru 16y ago
    Your first example is actually a tail call. It's just a tail call to the || operator. Every function has a tail call by definition.
    - eru 16y ago
      And the next two examples are tail calls of even and odd thanks to shortcutting of ||.
      - raganwald 16y ago
        Absolutely the calls to even and odd are tail calls because of the semantics of || in Ruby (and most other languages). I hope we agree that even and odd are still mutually tail recursive, because Mutual Tail Recursion is a special case of tail calling.
photon_off 16y ago
Perhaps I'm missing some larger point here, but if all tail recursive operations can be represented as loops, why not code them that way in the first place? It's probably better to know that recursive calls take up stack space on each call, than it is to know that tail recursion optimizes to a loop. If somebody could provide an example of a tail-recursive function that would be much more difficult to code as a loop, I'll eat my words.
- yason 16y ago
  As it happens, I've actually grown to like Clojure's recur more than tailcalls. And I much loved tailcalls over imperative loops earlier. recur is still functional, it resembles a loop but isn't one so nothing is mutated, and you can even nest them. And you can recur over a loop or the function itself. Handy.
  - _delirium 16y ago
    That's fairly common style in Scheme as well, fwiw; a "named let" is very similar to Clojure's recur, and some programmers prefer it over tailcalls, at least for many common recursion/iteration patterns.
- eru 16y ago
  Take a look at parsers. E.g. Parsec (http://www.haskell.org/haskellwiki/Parsec http://www.haskell.org/haskellwiki/Parsec). They probably have lots of tail-calls, and wouldn't look nice with loops. Some parsers also make use of continuation passing (http://en.wikipedia.org/wiki/Continuation-passing_style http://en.wikipedia.org/wiki/Continuation-passing_style), which only works with tail-call optimizations.
elbenshira 16y ago
Wow, this is basic stuff. I'm surprised that a researcher would get this wrong. Also, let us not forget that tail recursion is a specific form of the more general tail call optimization. For example, the following is two TCO-able functions calling each other: functionA(...): // do stuff return functionB(...) functionB(): // dostuff return functionA(...) Whether or not the compiler optimizes this, however, is a completely different question.

25 points by fogus 16y ago

It seems like a difference without distinction to me. I mean, sure, it doesn't fit the precise dictionary definition of tail recursion, but the function would be fairly trivial to implement in a purely tail recursive manner. As such, its close enough for most purposes.

kylec 16y ago
It matters when you have an interpreter/compiler that does tail-call optimization. If the function is tail recursive then the recursion will only use O(1) stack space, while non-tail recursive functions will use O(n).
bitwize 16y ago
Tail recursion means that there's nothing in the continuation of the recursive call besides a return from the outer call. This means that a compiler can optimize away the saving of a new stack frame for a recursive call, because the old stack frame of the enclosing call will never be used again. That's tail-call optimization. If there's stuff in between the return from the recursive call and the return from the enclosing call (like the multiply in this factorial example) then the old stack frame will have to be kept around which means you must use unoptimized recursive calls.
DrJokepu 16y ago
Sometimes it's trivial, sometimes it's not. Sometimes it's not even possible (e.g. the naive Fibionacci algorithm). Sometimes all you need to do is to add an accumulator argument to the recursive function. Still, it's not something that can be easily automated and I'm yet to see a compiler that does it automatically. In computer science (and generally, in mathematics), every word of the dictionary definition matter.
deleted 16y ago
[deleted]
ori_b 16y ago
It makes all the difference in the world - One can be converted by the compiler into a loop that will never use more than one function call's worth of stack, and the other must cause an unbounded amount of memory usage dependent on the input argument. In other words, it's the difference between O(n) and O(1) memory usage.
michaelcampbell 16y ago
> As such, its close enough for most purposes. Well, this purpose was to make it a tail call so that it could be optimized. Since it either is or it isn't, "close enough" to "is" is, sadly, "isn't". Which turns it from O(1) to O(n).

j_baker 16y ago

On the JVM, wouldn't * be an operator rather than a function? Would it even make a difference?

DrJokepu 16y ago
No. The very last instruction of tail recursion (on the recursive branch, not the base case of course) should be directly returning the return value of the recursively called function. Otherwise, you cannot overwrite the stack frame (in other words, you need to remember the values of temporary variables of previous iterations).
Hemospectrum 16y ago
At the assembly/bytecode level, you still have to save the return value of the recursive call and then do something to it, whereas a tail call wouldn't need to save any intermediate value because it would immediately return it as soon as it got it. I guess Java's infix notation kind of obscures this. This is one of the reasons why functional programmers prefer to consider everything a function. It's also why some languages (like Clojure) have special syntax for tail calls, with special error messages if you goof up the semantics.
- Uchikoma 16y ago
  I like this idea - never came up to me before n * fac(n-1) vs. * n fac(- n 1) or * (n, fac(n-1)) as a method call, which makes it clear * is the last function that's called.
- eru 16y ago
  Yes, in Lisp there's no real difference between * or car. In Haskell, which has more syntax, you can use * in infix notation, but so you can with other function. E.g. the function `on`. Quoting from the documentation: on :: (b -> b -> c) -> (a -> b) -> a -> a -> c (*) `on` f = \x y -> f x * f y. Typical usage: Data.List.sortBy (compare `on` fst).
CodeMage 16y ago
It wouldn't, because you would still have to do something else after the recursive call to your function. That would prevent you from applying tail-call optimization, which is the point behind making your function tail-recursive in the first place. For those who aren't familiar with tail-call optimization, here's a very simplified explanation: if the very last thing you do in a function is call it recursively, then instead of allocating the space for its local variables (and any other local state it might have) for another call, you can simply set the arguments to their new values, reset the local state and do an equivalent of "goto" to the beginning of the function.

deleted 16y ago

[deleted]

kenjackson 16y ago

One way that would make that particular example clearer is to convert the multiplication from an infix operation to a function call: return n == 0 ? 1 : n * fac(n -1); becomes return n == 0 ? 1 : multiply(n, fac(n -1); This makes it a fair bit clearer, IMO.

deleted 16y ago
[deleted]
- kenjackson 16y ago
  [no longer applies to the comment]
barrkel 16y ago
I suspect a better approach is to make expected tail recursion a language feature, and have the compiler emit an error if the returned expression is not in fact valid for a tail call. Imagine if it were 'treturn' or something. It's not something that bites people who have been around this mulberry bush before, but I think it can very likely catch problems that novices have, thinking they're writing an O(1) space solution but actually using O(n) stack.
- eru 16y ago
  OK. But then, even if somebody is using `return', and its tail-recursive, it should be optimized. (`return' should just not raise an error, if it's not tail-recursice.)

Roboprog 16y ago

A comment on the site itself noted that tail recursion does not imply parallelization -- in fact, I would make a stronger statement that it forces serial execution, at least as far as funneling results of one "iteration" into the next. The benefit, as "everybody" here of course already knows, is to reduce memory (call stack) usage. Knowing how to implement tail recursion allows you to write in an "assign only once" type of language, without blowing up the stack. And using such "invariant symbols" in a routine allows the compiler/interpreter to seek parallelization at other points in the function on your behalf. OK, so I just contradicted myself, but the point is there is an rather indirect connection between tail recursion and parallelization.

sedachv 16y ago

No one addressed the parallelization claim, so here goes: The ability to parallelize purely functional code comes from the Church-Rosser theorem (http://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem http://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem), which states that you can do beta reductions in any order in the lambda calculus and get the same term. The thing with tail-recursive code is precisely that there is only one way to do a reduction - the function has to call itself at the end. That's what makes tail-recursive code "iterative." As soon as you introduce multiple reduction paths, you need a stack for the intermediate results - think of for example a recursive divide-and-conquer algorithm. This Kornelius Fuhrer dude shouldn't be writing articles on parallel programming, he should be reading books about it.

barrkel 16y ago
I can, however, see a compiler turning simple cases of tail recursion into recurrence relations, and re-extracting the loop, but it's a relatively long way to go to get back that iterative bit of the problem, especially as a language in which tail recursion is often used probably won't be working with mutable arrays as often - a loop over input and output arrays being probably the easiest parallelization candidate.
- sedachv 16y ago
  I never thought about it that way. That's quite clever and out of the box! Guy Steele gave a very good talk about the problem (basically, "tail recursion considered harmful") and solution ("divide and conquer") at ICFP last year: http://docs.google.com/viewer?a=v&q=cache:bBDVKW8DP6UJ:labs.oracle.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf+foldr+considered+harmful&hl=en&gl=ca&pid=bl&srcid=ADGEESiHWEmfK12_eOyYM0465fA2ltUZLfPwQxtlNADEVwhJgdiIFKB1_YRvSv064kacRgLtLX7CWHrBBi72WaPrlXcrQqRXaqJB6-DSA10Sej9jFkXJM7GVPVx-VUfkmho-s5sduHga&sig=AHIEtbTLZ4NCoMphAYt6CkQ7PuspHJqNCw http://docs.google.com/viewer?a=v&q=cache:bBDVKW8DP6UJ:l... APL-style operators (map/reduce, paralations, NESL, etc.) are definitely the way to go. Not only do you get parallelization "for free," but optimizations like map fusion (see http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance http://www.randomhacks.net/articles/2007/02/10/map-fusion-an..., and Rich Waters' earlier work on SERIES: http://series.sourceforge.net/ http://series.sourceforge.net/) become easy - something like that is almost impossible to do with loop analysis. All that, and you end up with clearer, shorter code. Due to all these reasons, I'm convinced that automatic loop parallelization is the biggest waste of time in parallel computing research.

sophacles 16y ago

In the example case, and many others, the tail-recursive version is the simple application of an accumulator. So for the factorial example, an accumulator version would be (in haskell since I don't know the example language very well): fac1 0 = 1 fac1 n = (*) n (fac1 ((-) n 1)) -- tail-recursive fac2 0 acc = acc fac2 n acc = fac2 ((-)n 1) ((*) acc n) To me, something in with a pattern of: f v = g v (f (t v)) where f, g and t are functions (t is a transform on a, in the factorial case it is (-), Can usually be turned into the form (mechanically even): f v acc = f (t v) (g v acc) Does this hold for all cases or am i missing something? If it does hold, could a language just implement the TCO for it, and therefore couldn't we just consider the very first implementation of fac1 to be tail-recursive? edit: It is ugly but changed my exmple code to match the pattern i describe exactly.

Psyonic 16y ago
I believe this has some issues if the operation isn't commutative. For example: blah 0 = [] blah n = (++) [n] (blah ((-) n 1)) -- blah 5 -> [5,4,3,2,1] blah2 0 acc = acc blah2 n acc = blah2 ((-) n 1) ((++) [n] acc) -- blah2 5 [] -> [1,2,3,4,5] If we changed the tail to: blah2 (n-1) ((++) acc [n]) it would work in this case, but then we've flipped the arguments, and I have a feeling we could come up with a function where simply flipping the arguments won't work, though I can't think of one at the moment.
- sophacles 16y ago
  Good point! It becomes hard to do mechanical transforms like I suggested when you have to keep track of properties like this for every function. Thanks!
  - Psyonic 16y ago
    Ya that's the problem. Here's what I originally intended to write, but couldn't think of how to do cons in haskell so I used list addition. With cons (:), you can't rewrite it with the arguments swapped, so no simple mechanical transform will be able to fix this. blah 0 = [] blah n = (:) n (blah ((-) n 1)) -- blah 5 -> [5,4,3,2,1] blah2 0 acc = acc blah2 n acc = blah2 ((-) n 1) ((:) n acc) -- blah2 5 [] -> [1,2,3,4,5]

geuis 16y ago

I don't understand what his last statement means: "So please, do not call all functions where the last function call in your source code is a call to itself, tail recursive. A function is tail recursive, if the last operation is a function call to itself." It reads to me as "Don't call functions that call themselves last tail recursive. A function is tail recursive if it calls itself last." That's saying the same thing, if my reading of it is right. His oddly-placed commas don't help.

Jtsummers 16y ago
I can't read the article (silly work web filters), but if you're quoting him correctly then I have an idea. ( function foo(n) { ... return n+foo(n-1); } is not tail recursive because the last operation is not the recursive function call, but rather the addition. function bar(n,acc) { ... return bar(n-1,acc+n); } is tail recursive because the last operation is now the recursive function call.
akeefer 16y ago
He's pointing out that the order of statements in the source code doesn't necessary correspond to the order of evaluation. In this case even though the function call is the last statement in the source code, it's actually an argument to the multiplication, and the multiplication is the last operation being executed. That's non-obvious when just looking at the code, since the function call looks like it's last.

btilly 16y ago

The correction is incorrect. A function is tail recursive when the last thing it does is call some function, possibly different. Yes, you can have a mess of different functions that are mutually tail recursive. For an example of how this comes up, think "state machines" with each call being another state transition.

raganwald 16y ago
I am used to the term Tail Call for a function that returns the result of calling another function. Tail Recursion is then a special case where a function makes a Tail Call to itself. Mutual Tail Recursion is another special case where multiple functions make tail calls to each other in such a way that a function will end up calling itself indirectly. Not a tail call: var even = function (x) { return x == 0 || !even(x-1); } Mutually Tail Recursive: var even = function (x) { return x == 0 || odd(x-1); } var odd = function (x) { return x == 1 || even(x-1); }
- eru 16y ago
  Your first example is actually a tail call. It's just a tail call to the || operator. Every function has a tail call by definition.
  - eru 16y ago
    And the next two examples are tail calls of even and odd thanks to shortcutting of ||.
    - raganwald 16y ago
      Absolutely the calls to even and odd are tail calls because of the semantics of || in Ruby (and most other languages). I hope we agree that even and odd are still mutually tail recursive, because Mutual Tail Recursion is a special case of tail calling.

photon_off 16y ago

Perhaps I'm missing some larger point here, but if all tail recursive operations can be represented as loops, why not code them that way in the first place? It's probably better to know that recursive calls take up stack space on each call, than it is to know that tail recursion optimizes to a loop. If somebody could provide an example of a tail-recursive function that would be much more difficult to code as a loop, I'll eat my words.

yason 16y ago
As it happens, I've actually grown to like Clojure's recur more than tailcalls. And I much loved tailcalls over imperative loops earlier. recur is still functional, it resembles a loop but isn't one so nothing is mutated, and you can even nest them. And you can recur over a loop or the function itself. Handy.
- _delirium 16y ago
  That's fairly common style in Scheme as well, fwiw; a "named let" is very similar to Clojure's recur, and some programmers prefer it over tailcalls, at least for many common recursion/iteration patterns.
eru 16y ago
Take a look at parsers. E.g. Parsec (http://www.haskell.org/haskellwiki/Parsec http://www.haskell.org/haskellwiki/Parsec). They probably have lots of tail-calls, and wouldn't look nice with loops. Some parsers also make use of continuation passing (http://en.wikipedia.org/wiki/Continuation-passing_style http://en.wikipedia.org/wiki/Continuation-passing_style), which only works with tail-call optimizations.

elbenshira 16y ago

Wow, this is basic stuff. I'm surprised that a researcher would get this wrong. Also, let us not forget that tail recursion is a specific form of the more general tail call optimization. For example, the following is two TCO-able functions calling each other: functionA(...): // do stuff return functionB(...) functionB(): // dostuff return functionA(...) Whether or not the compiler optimizes this, however, is a completely different question.