R: the level of recursion depth allowed differs when calling a local helper function
this is a purely academic question:
I recently worked with languages that use tail recursion optimization. For practice, I wrote two recursive implementations of summary functions in R, one of which is tail recursive. I quickly realized that there is no tail recursion optimization in P. I can live with it. However, I also noticed different levels of depth allowed when using the local tail recursion helper.
Here is the code:
## Recursive
sum <- function (i, end, fun){
if (i>=end) 0
else fun(i) + sum(i+1, end, fun)
}
## Tail recursive
sum_tail <- function (i, end, fun){
sum_helper<- function(i, acc){
if (i>=end) acc
else sum_helper(i+1, acc+fun(i))
}
sum_helper(i, 0)
}
## Simple example
harmonic <- function(k){
return(1/(k))
}
print(sum(1, 1200, harmonic)) # <- This works fine, but is close to the limit
# print(sum_tail(1, 1200, harmonic)) <- This will crash
print(sum_tail(1, 996, harmonic)) # <- This is the deepest allowed
I'm pretty intrigued. Can anyone explain this behavior or point me to a doc explaining how the allowed recursion depth is calculated?
source to share
I'm not sure about R's internal implementation of the call stack, but it is pretty obvious from here that there is a maximum stack depth. (Many languages have this for various reasons, mostly memory related and detecting infinite recursion.) You can set it with options()
, and the default seems to be platform dependent - on my machine I can do it print(sum_tail(1, 996, harmonic))
without difficulty.
Sidebar: You really shouldn't be calling your naive implementation sum()
, because you end up shading the inline. I know that you are just playing around with recursion here, but you should also avoid doing your own implementation sum()
- it is not provided simply as a convenience function, and also because it is not trivial to implement the sum()
floating point numeric version .
In your naive implementation, the call fun()
returns before the recursive call - this means that each recursive call increases the call stack depth by exactly 1. Otherwise, you have an additional function call this wait for evaluation. For more details, you should look into how R handles closures and how lazy / eager evaluation is handled in R. If I recall correctly, R uses environments (roughly R-representation of scope and deeply related to closures) to wrap arguments in certain situations and defer evaluating them, thereby effectively using lazy evaluation. There is a lot of information about internal R functions here, see here for a quick overview of argument evaluation... I'm not sure how precise I am on the details, but it seems that the tail call arguments themselves are pushed onto the call stack, thereby increasing the call stack depth by more than 1.
Sidebar Two: I don't remember very well how R implements this, and I know that putting helper functions in the body is common practice, but placing the helper function definition in a recursive call can result in every recursive call redefining the helper function. This can interact differently with how environments and closures are handled, but I'm not sure.
Functions traceback()
and trace()
can be useful in learning call behavior if you are interested in learning more about the details.
source to share