Menu
Does R support proper tail recursion and where can I find documentation about this?
983
Tail-recursive functions are considered better than non-tail-recursive functions — the compiler can easily optimize the tail-recursive function as there is nothing left to do in the current function after the recursive call. Hence, the function's stack frame need not be saved.
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.
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.
smp of tail-recursive version will use 2.5G ~ 3G memory while the body-recursive only use around 1G.
It's quite easy to find out that R does not support tail recursion optimization:
f <- function(n) {
if (n != 0) f(n-1)
}
f(100000)
# Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
Had tail calls been optimized to jumps, then this function would have terminated without problems.
95
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
