3 ms·

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

by j_baker 16y ago

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.

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

by j_baker 16y ago

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

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.