Does java support and optimize away tail-recursive calls?
up vote
17
down vote
favorite
Say I got a recursive function that is tail-recursive.
System.out.println( sum(Arrays.asList(0, 1, 2, 3, 4, 5)) );
int sum(List<Integer> integers) {
if (integers.isEmpty())
return 0;
else
return integers.get(0) + sum(integers.subList(1, integers.size()));
}
I wonder if this function sum will grow on stack or will it be changed to a loop (since it is a tail-recursive function)?
I have just read that Scala detects such calls and optimizes it but is this a Scala-only thing or JVM in general?
java scala optimization recursion jvm
asked Dec 29 '13 at 15:33
user3073853
10519
|
show 1 more comment
up vote
17
down vote
favorite
Say I got a recursive function that is tail-recursive.
System.out.println( sum(Arrays.asList(0, 1, 2, 3, 4, 5)) );
int sum(List<Integer> integers) {
if (integers.isEmpty())
return 0;
else
return integers.get(0) + sum(integers.subList(1, integers.size()));
}
I wonder if this function sum will grow on stack or will it be changed to a loop (since it is a tail-recursive function)?
I have just read that Scala detects such calls and optimizes it but is this a Scala-only thing or JVM in general?
java scala optimization recursion jvm
asked Dec 29 '13 at 15:33
user3073853
10519
12
I'm pretty sure that this function is NOT tail-recursive. After nested call to sum(), there is still need to add something to the return value of that call.
– Novakov
Dec 29 '13 at 15:35
6
That's not a tail call.
– user395760
Dec 29 '13 at 15:35
1
Regardless, HotSpot does not support TCO: stackoverflow.com/q/3616483/139010
– Matt Ball
Dec 29 '13 at 15:35
1
Creating a subList object is more expensive than the recursion (assuming you done run out of stack) Of course the most efficient option is plain iteration.
– Peter Lawrey
Dec 29 '13 at 16:03
2
Given that you are interested in this style of programming, is there a reason why you can't just use Scala? The equivalent of the above (the whole thing) would beprintln((0 to 5).sum). If you consider using the sum() method cheating, you could generate the sum using a fold:(0 /: (0 to 5))(_+_). As a method, a somewhat more general version of the above isdef sum( xs:Seq[Int] ):Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail). Or you could write a tail-recursive version and it would actually get optimized (by scalac).
– AmigoNico
Dec 30 '13 at 2:13
|
show 1 more comment
up vote
17
down vote
favorite
up vote
17
down vote
favorite
Say I got a recursive function that is tail-recursive.
System.out.println( sum(Arrays.asList(0, 1, 2, 3, 4, 5)) );
int sum(List<Integer> integers) {
if (integers.isEmpty())
return 0;
else
return integers.get(0) + sum(integers.subList(1, integers.size()));
}
I wonder if this function sum will grow on stack or will it be changed to a loop (since it is a tail-recursive function)?
I have just read that Scala detects such calls and optimizes it but is this a Scala-only thing or JVM in general?
java scala optimization recursion jvm
asked Dec 29 '13 at 15:33
user3073853
10519
Say I got a recursive function that is tail-recursive.
System.out.println( sum(Arrays.asList(0, 1, 2, 3, 4, 5)) );
int sum(List<Integer> integers) {
if (integers.isEmpty())
return 0;
else
return integers.get(0) + sum(integers.subList(1, integers.size()));
}
I wonder if this function sum will grow on stack or will it be changed to a loop (since it is a tail-recursive function)?
I have just read that Scala detects such calls and optimizes it but is this a Scala-only thing or JVM in general?
java scala optimization recursion jvm
java scala optimization recursion jvm
asked Dec 29 '13 at 15:33
user3073853
10519
asked Dec 29 '13 at 15:33
user3073853
10519
edited Dec 29 '13 at 20:06
asked Dec 29 '13 at 15:33
user3073853
10519
asked Dec 29 '13 at 15:33
user3073853
10519
asked Dec 29 '13 at 15:33
user3073853
10519
10519
12
I'm pretty sure that this function is NOT tail-recursive. After nested call to sum(), there is still need to add something to the return value of that call.
– Novakov
Dec 29 '13 at 15:35
6
That's not a tail call.
– user395760
Dec 29 '13 at 15:35
1
Regardless, HotSpot does not support TCO: stackoverflow.com/q/3616483/139010
– Matt Ball
Dec 29 '13 at 15:35
1
Creating a subList object is more expensive than the recursion (assuming you done run out of stack) Of course the most efficient option is plain iteration.
– Peter Lawrey
Dec 29 '13 at 16:03
2
Given that you are interested in this style of programming, is there a reason why you can't just use Scala? The equivalent of the above (the whole thing) would beprintln((0 to 5).sum). If you consider using the sum() method cheating, you could generate the sum using a fold:(0 /: (0 to 5))(_+_). As a method, a somewhat more general version of the above isdef sum( xs:Seq[Int] ):Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail). Or you could write a tail-recursive version and it would actually get optimized (by scalac).
– AmigoNico
Dec 30 '13 at 2:13
|
show 1 more comment
12
I'm pretty sure that this function is NOT tail-recursive. After nested call to sum(), there is still need to add something to the return value of that call.
– Novakov
Dec 29 '13 at 15:35
6
That's not a tail call.
– user395760
Dec 29 '13 at 15:35
1
Regardless, HotSpot does not support TCO: stackoverflow.com/q/3616483/139010
– Matt Ball
Dec 29 '13 at 15:35
1
Creating a subList object is more expensive than the recursion (assuming you done run out of stack) Of course the most efficient option is plain iteration.
– Peter Lawrey
Dec 29 '13 at 16:03
2
Given that you are interested in this style of programming, is there a reason why you can't just use Scala? The equivalent of the above (the whole thing) would beprintln((0 to 5).sum). If you consider using the sum() method cheating, you could generate the sum using a fold:(0 /: (0 to 5))(_+_). As a method, a somewhat more general version of the above isdef sum( xs:Seq[Int] ):Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail). Or you could write a tail-recursive version and it would actually get optimized (by scalac).
– AmigoNico
Dec 30 '13 at 2:13
12
12
I'm pretty sure that this function is NOT tail-recursive. After nested call to sum(), there is still need to add something to the return value of that call.
– Novakov
Dec 29 '13 at 15:35
I'm pretty sure that this function is NOT tail-recursive. After nested call to sum(), there is still need to add something to the return value of that call.
– Novakov
Dec 29 '13 at 15:35
6
6
That's not a tail call.
– user395760
Dec 29 '13 at 15:35
That's not a tail call.
– user395760
Dec 29 '13 at 15:35
1
1
Regardless, HotSpot does not support TCO: stackoverflow.com/q/3616483/139010
– Matt Ball
Dec 29 '13 at 15:35
Regardless, HotSpot does not support TCO: stackoverflow.com/q/3616483/139010
– Matt Ball
Dec 29 '13 at 15:35
1
1
Creating a subList object is more expensive than the recursion (assuming you done run out of stack) Of course the most efficient option is plain iteration.
– Peter Lawrey
Dec 29 '13 at 16:03
Creating a subList object is more expensive than the recursion (assuming you done run out of stack) Of course the most efficient option is plain iteration.
– Peter Lawrey
Dec 29 '13 at 16:03
2
2
Given that you are interested in this style of programming, is there a reason why you can't just use Scala? The equivalent of the above (the whole thing) would be
println((0 to 5).sum). If you consider using the sum() method cheating, you could generate the sum using a fold: (0 /: (0 to 5))(_+_). As a method, a somewhat more general version of the above is def sum( xs:Seq[Int] ):Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail). Or you could write a tail-recursive version and it would actually get optimized (by scalac).– AmigoNico
Dec 30 '13 at 2:13
Given that you are interested in this style of programming, is there a reason why you can't just use Scala? The equivalent of the above (the whole thing) would be
println((0 to 5).sum). If you consider using the sum() method cheating, you could generate the sum using a fold: (0 /: (0 to 5))(_+_). As a method, a somewhat more general version of the above is def sum( xs:Seq[Int] ):Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail). Or you could write a tail-recursive version and it would actually get optimized (by scalac).– AmigoNico
Dec 30 '13 at 2:13
|
show 1 more comment
2 Answers
2
active
oldest
votes
up vote
17
down vote
accepted
Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)
But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.
Look at this:
int sum(List<Integer> integers) {
return sum(integers, 0);
}
int sum(List<Integer> integers, int sumSoFar) {
if (integers.isEmpty())
return sumSoFar;
else
return sum(
integers.subList(1, integers.size()),
sumSoFar + integers.get(0)
);
}
See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.
In your snippet the stack frame would probably have to exist as long as the recursive call..
answered Dec 29 '13 at 15:43
emesx
8,93664586
3
you probably know this, but anyways,@tailrecis used only to enforce optimized code -- if compiler is not able to do so, it will throw compilation error. But still, code will be optimized if it is possible to do, whether such annotation is presented or not.
– om-nom-nom
Dec 29 '13 at 19:28
1
@om-nom-nom yes, good that you pointed out this here.@tailrecin Scala is similar to@Overridein Java (in terms of presence and compiler actions).
– emesx
Dec 29 '13 at 20:04
add a comment |
up vote
3
down vote
According to this article from April 2014:
It's important to note that this isn't a bug in the JVM. It's an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it's on a list of things to be added to the JVM, but it's just not a high-priority item.
answered Jan 27 '15 at 18:17
lbalazscs
13.6k73044
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
17
down vote
accepted
Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)
But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.
Look at this:
int sum(List<Integer> integers) {
return sum(integers, 0);
}
int sum(List<Integer> integers, int sumSoFar) {
if (integers.isEmpty())
return sumSoFar;
else
return sum(
integers.subList(1, integers.size()),
sumSoFar + integers.get(0)
);
}
See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.
In your snippet the stack frame would probably have to exist as long as the recursive call..
answered Dec 29 '13 at 15:43
emesx
8,93664586
3
you probably know this, but anyways,@tailrecis used only to enforce optimized code -- if compiler is not able to do so, it will throw compilation error. But still, code will be optimized if it is possible to do, whether such annotation is presented or not.
– om-nom-nom
Dec 29 '13 at 19:28
1
@om-nom-nom yes, good that you pointed out this here.@tailrecin Scala is similar to@Overridein Java (in terms of presence and compiler actions).
– emesx
Dec 29 '13 at 20:04
add a comment |
up vote
17
down vote
accepted
Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)
But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.
Look at this:
int sum(List<Integer> integers) {
return sum(integers, 0);
}
int sum(List<Integer> integers, int sumSoFar) {
if (integers.isEmpty())
return sumSoFar;
else
return sum(
integers.subList(1, integers.size()),
sumSoFar + integers.get(0)
);
}
See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.
In your snippet the stack frame would probably have to exist as long as the recursive call..
answered Dec 29 '13 at 15:43
emesx
8,93664586
3
you probably know this, but anyways,@tailrecis used only to enforce optimized code -- if compiler is not able to do so, it will throw compilation error. But still, code will be optimized if it is possible to do, whether such annotation is presented or not.
– om-nom-nom
Dec 29 '13 at 19:28
1
@om-nom-nom yes, good that you pointed out this here.@tailrecin Scala is similar to@Overridein Java (in terms of presence and compiler actions).
– emesx
Dec 29 '13 at 20:04
add a comment |
up vote
17
down vote
accepted
up vote
17
down vote
accepted
Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)
But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.
Look at this:
int sum(List<Integer> integers) {
return sum(integers, 0);
}
int sum(List<Integer> integers, int sumSoFar) {
if (integers.isEmpty())
return sumSoFar;
else
return sum(
integers.subList(1, integers.size()),
sumSoFar + integers.get(0)
);
}
See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.
In your snippet the stack frame would probably have to exist as long as the recursive call..
answered Dec 29 '13 at 15:43
emesx
8,93664586
Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)
But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.
Look at this:
int sum(List<Integer> integers) {
return sum(integers, 0);
}
int sum(List<Integer> integers, int sumSoFar) {
if (integers.isEmpty())
return sumSoFar;
else
return sum(
integers.subList(1, integers.size()),
sumSoFar + integers.get(0)
);
}
See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.
In your snippet the stack frame would probably have to exist as long as the recursive call..
answered Dec 29 '13 at 15:43
emesx
8,93664586
answered Dec 29 '13 at 15:43
emesx
8,93664586
answered Dec 29 '13 at 15:43
emesx
8,93664586
answered Dec 29 '13 at 15:43
emesx
8,93664586
8,93664586
3
you probably know this, but anyways,@tailrecis used only to enforce optimized code -- if compiler is not able to do so, it will throw compilation error. But still, code will be optimized if it is possible to do, whether such annotation is presented or not.
– om-nom-nom
Dec 29 '13 at 19:28
1
@om-nom-nom yes, good that you pointed out this here.@tailrecin Scala is similar to@Overridein Java (in terms of presence and compiler actions).
– emesx
Dec 29 '13 at 20:04
add a comment |
3
you probably know this, but anyways,@tailrecis used only to enforce optimized code -- if compiler is not able to do so, it will throw compilation error. But still, code will be optimized if it is possible to do, whether such annotation is presented or not.
– om-nom-nom
Dec 29 '13 at 19:28
1
@om-nom-nom yes, good that you pointed out this here.@tailrecin Scala is similar to@Overridein Java (in terms of presence and compiler actions).
– emesx
Dec 29 '13 at 20:04
3
3
you probably know this, but anyways,
@tailrec is used only to enforce optimized code -- if compiler is not able to do so, it will throw compilation error. But still, code will be optimized if it is possible to do, whether such annotation is presented or not.– om-nom-nom
Dec 29 '13 at 19:28
you probably know this, but anyways,
@tailrec is used only to enforce optimized code -- if compiler is not able to do so, it will throw compilation error. But still, code will be optimized if it is possible to do, whether such annotation is presented or not.– om-nom-nom
Dec 29 '13 at 19:28
1
1
@om-nom-nom yes, good that you pointed out this here.
@tailrec in Scala is similar to @Override in Java (in terms of presence and compiler actions).– emesx
Dec 29 '13 at 20:04
@om-nom-nom yes, good that you pointed out this here.
@tailrec in Scala is similar to @Override in Java (in terms of presence and compiler actions).– emesx
Dec 29 '13 at 20:04
add a comment |
up vote
3
down vote
According to this article from April 2014:
It's important to note that this isn't a bug in the JVM. It's an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it's on a list of things to be added to the JVM, but it's just not a high-priority item.
answered Jan 27 '15 at 18:17
lbalazscs
13.6k73044
add a comment |
up vote
3
down vote
According to this article from April 2014:
It's important to note that this isn't a bug in the JVM. It's an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it's on a list of things to be added to the JVM, but it's just not a high-priority item.
answered Jan 27 '15 at 18:17
lbalazscs
13.6k73044
add a comment |
up vote
3
down vote
up vote
3
down vote
According to this article from April 2014:
It's important to note that this isn't a bug in the JVM. It's an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it's on a list of things to be added to the JVM, but it's just not a high-priority item.
answered Jan 27 '15 at 18:17
lbalazscs
13.6k73044
According to this article from April 2014:
It's important to note that this isn't a bug in the JVM. It's an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it's on a list of things to be added to the JVM, but it's just not a high-priority item.
answered Jan 27 '15 at 18:17
lbalazscs
13.6k73044
answered Jan 27 '15 at 18:17
lbalazscs
13.6k73044
answered Jan 27 '15 at 18:17
lbalazscs
13.6k73044
answered Jan 27 '15 at 18:17
lbalazscs
13.6k73044
13.6k73044
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f20826786%2fdoes-java-support-and-optimize-away-tail-recursive-calls%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
12
I'm pretty sure that this function is NOT tail-recursive. After nested call to sum(), there is still need to add something to the return value of that call.
– Novakov
Dec 29 '13 at 15:35
6
That's not a tail call.
– user395760
Dec 29 '13 at 15:35
1
Regardless, HotSpot does not support TCO: stackoverflow.com/q/3616483/139010
– Matt Ball
Dec 29 '13 at 15:35
1
Creating a subList object is more expensive than the recursion (assuming you done run out of stack) Of course the most efficient option is plain iteration.
– Peter Lawrey
Dec 29 '13 at 16:03
2
Given that you are interested in this style of programming, is there a reason why you can't just use Scala? The equivalent of the above (the whole thing) would be
println((0 to 5).sum). If you consider using the sum() method cheating, you could generate the sum using a fold:(0 /: (0 to 5))(_+_). As a method, a somewhat more general version of the above isdef sum( xs:Seq[Int] ):Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail). Or you could write a tail-recursive version and it would actually get optimized (by scalac).– AmigoNico
Dec 30 '13 at 2:13