Recursion in R error

Question

I have the following recursive function:

tamanho <- function(v){
  if (is.null(v)){
    return(0)
  }
  i <- tamanho(v[-1])+1
  return(i)
}

I’m using Rstudio, and when I call the function with this example:

tamanho(c(1,2,3,5))

gives the following error, and the R "reset":

R Session Aborted
R encountered a fatal error.
The Session was terminated.
[Start New Session]

Answer 1

Your function has a logic problem. If v is null, it’s all right: it stops. But if v not null, it will continue to recur indefinitely. Suppose, as in your example, that v <- c(1,2,3,5):

v <- c(1, 2, 3, 5)
v[-1]
[1] 2 3 5

v[-1] is the vector v without the first element. The second step of your recursive function is to delete the second element, which is equivalent to

v[-1][-1]
[1] 3 5

And that works, because R understands that v[-1] is a vector and therefore it is possible to remove its first position, as it was possible to do this with v. But look what happens if we do it more often:

v
[1] 1 2 3 5
v[-1]
[1] 2 3 5
v[-1][-1]
[1] 3 5
v[-1][-1][-1]
[1] 5
v[-1][-1][-1][-1]
numeric(0)
v[-1][-1][-1][-1][-1]
numeric(0)
v[-1][-1][-1][-1][-1][-1]
numeric(0)

Realize that from the moment v is exhausted, the R continues to try to calculate its size, even if there is no size to be calculated, which is what occurs from v[-1][-1][-1][-1]. This is because, even having no element, v[-1][-1][-1][-1] is not null:

is.null(v[-1][-1][-1][-1])
[1] FALSE

Therefore, your program has no stopping criteria, because is.null does not serve the desired purpose. So much so that when running your original code in the terminal, instead of a crash like in Rstudio, the error response I get is the following:

tamanho(c(1, 2, 3, 5))
Error: C stack usage  7969280 is too close to the limit

That is, the stack bursts (aka stack overflow).

You can fix this with a little change in your code:

tamanho <- function(v){
  i <- 0
  if (!identical(v, numeric(0))){
    i <- tamanho(v[-1]) + 1
  }
  return(i)
}

v <- c(1, 2, 3, 5)
tamanho(v)
[1] 4

identical(v, numeric(0)) will test the recursion of v arrives in numeric(0) at some point. ! will deny this. Therefore, recursion will stop only when numeric(0) is true.

Due to the test use numeric(0) as a stop condition, this code only serves to calculate lengths of numerical vectors. It is up to the reader to implement a general version of it, for character vectors, integers, logic etc.