2 ms·
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 d
by 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 agoI 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 agoYour 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 agoAnd the next two examples are tail calls of even and odd thanks to shortcutting of ||.
- raganwald 16y agoAbsolutely 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.