Menu
check out this Scala-code:
def rec(n: Int) {
if (n > 1) {
val d = n / 2
rec(d)
// if (d > 1) // abort loop
rec(n/d)
}
}This code will result in an endless loop. Owing to tail recursive optimization I don't get a StackOverflowError.
Decompiled with jad I got this Java-code:
public void rec(int n)
{
int d;
for(; n > 1; n /= d)
{
int i = n;
d = i / 2;
rec(d);
}
}In the last line of the loop the method calls itself therefore I don't understand the tail call position. Anyone who can explain this?
817
An easy way to tell if a recursive function is a tail recursive is if it returns a concrete value in the base case. Meaning that it doesn't return 1 or true or anything like that. It will more than likely return some variant of one of the method parameters.
Some programming languages are tail-recursive, essentially this means is that they're able to make optimizations to functions that return the result of calling themselves. That is, the function returns only a call to itself.
Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. For example the following C++ function print() is tail recursive.
The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. When one function is called, its address is stored inside the stack. So if it is tail recursion, then storing addresses into stack is not needed.
There is no tail call in case of rec(d). For rec(N) (where N > 1) stack doesn't grow anymore after log2(N) calls (because after that n is equal to 2 or 3 forever, and d is 1). After that it's just infinite loop with inner rec(1) call which immediately returns each time. That's why there is not stack overflow.
180
In recursive form of your method you have two recursive calls. StackOverflowError is caused by the last of them.
Due to tail recursion optimization, that last call turns into loop (while the first call is kept recursive), therefore you have infinite loop instead of infinite recursion, and StackOverflowError doesn't happen.
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
