How to efficiently grow a vector in R?

Question

Let's say you have a function that takes a number as an input and outputs a vector. However, the output vector size depends on the input and you can't calculate it before the function.

For example, take the 3N+1 famous algorithm. A simple implementation of that algorithm, returning the whole path until 1 could look like this:

compute <- function(x) {
  if (x %% 2 == 0)
    return(x / 2)
  return(3*x + 1)
}

algo <- function(x) {
  if (x == 1)
    return(1)

  output <- x
  while(x != 1) {
    x <- compute(x)
    output <- c(output, x)
  }

  return(output)
}

The algo function returns the whole path of an input X to 1, according to the function. As you can tell, the output variable grows dynamically, using the c() (combine) function.

Are there any alternatives to this? Is growing a list faster? Should I adopt some classic dynamic vector logic, such as initializing an empty N-sized vector and double it everytime it goes full?

EDIT: Please don't mind trying to optimize the way my helper functions are structured. I get it, but that's not the point here! I am only concerned about the c() function and an alternative to it.

Answer 1

Update

As per your edit, maybe you can check the following solution

algo_TIC2 <- function(x) {
  res <- x
  repeat {
    u <- tail(res, 1)
    if (u != 1) {
      res[length(res) + 1] <- if (u %% 2) 3 * u + 1 else u / 2
    } else {
      return(res)
    }
  }
}

---

You can use recursions like below

compute <- function(x) if (x %% 2) 3*x + 1 else x / 2
algo_TIC1 <- function(x) {
  if (x == 1) {
    return(1)
  }
  c(x, algo_TIC1(compute(x)))
}

and you will see

> algo_TIC1(3000)
 [1] 3000 1500  750  375 1126  563 1690  845 2536 1268  634  317  952  476  238
[16]  119  358  179  538  269  808  404  202  101  304  152   76   38   19   58
[31]   29   88   44   22   11   34   17   52   26   13   40   20   10    5   16
[46]    8    4    2    1

---

If you don't want any helper function, i.e., compute, you can try

algo_TIC1 <- function(x) {
  if (x == 1) {
    return(1)
  }
  c(x, algo_TIC1(if (x %% 2) 3*x + 1 else x / 2))
}