Are Recursive Functions Used in R

Are recursive functions used in R?

For calculation of integer factorial, the recursive implementation is slower and more complex. Invariably, iteration is used in production code.

The factorial function you refer to is in the base package. It operates on real values rather than integers, hence that implementation. Its documentation states:

factorial(x) (x! for non-negative
integer x) is defined to be gamma(x+1)

A more interesting example is code to implement the Fibonnaci series which is extraordinarily wasteful when implemented with a naive recursion. The recursive approach can be made efficient through memoization but simple iteration is always to be preferred if performance is at stake.

Another common algorithm that is expressed naturally in a recursive way is Quicksort. This can, like all algorithms be implemented without recursion, but is quite complex to do so. There is little benefit in using a non-recursive Quicksort and so it's common to use the naive recursive implementation.

Recursion is a good implementation choice:

if performance is not compromised, and
if it is more natural (hence easier to verify and maintain) to implement recursively.

R: Beginner Question: Recursive Function On Function

Welcome to SO, thank you for a well formulated question.

First things straight. Recursion refers to the calling of a function within the same function as in the (not very explicit) example below:

f <- function(x){
    some code
    n <- f(x2)
    some more code
    return(x3)
}

Now for your problem. You're close to the answer you want. Three things got messed up in the process,

Remember your parenthesis.
Returning the output
Resetting the number at each iteration.

For 1. R reads code left to right, and will be very strict in how it calculates your code. 1:N/2 is equivalent to 1: N/2 which is equivalent to c(1, 2, ..., N) / 2. You're looking for 1:(N/2) or seq(1, N/2), and you likely would like to use either floor or ceiling for rounding uneven results of N/2, such as 5/2=2.5, 13/2=6.5 etc.

For 2. you are currently not returning anything from your function. In R you can explicitly return a value using return(...), or you can simply type out the object/number as the last thing in your function.

For 3, note that in the outer loop, you are calling number <- list(). At each iteration of the outer loop, this will reset the list of counts, thus removing any previous answer. This should be moved

Putting these together, getting the piece of code right amounts to the example below:

f <- function (N) {
  number <- list() # <=== initiate your canister only once.
  for (mm in 1:(N/2)) { #<=== remember parenthesis. Or use seq(1, N/2)
    count <- 0
    for (nn in 1:100) {
      a <- sample(1:N)
      b <- a [1:mm] 
      c <- a [mm+1:N]
      pass <- which(c>=max(b))
      if (length(pass) >= 1) {
        count <- count + 1
      }
    }
    number[mm] <- count
  }
  number #<== or return(number)
}

I wouldn't mind giving a few general suggestions, but it isn't quite clear to me, what the greater picture of the function is.

Recursive functions and global vs. local variables

You can use the local function to do the same thing but without modifying the global environment:

testfun <- local({
  i <- 1
  function( depth= 0 ) {
    i <<- i + 1
    cat( sprintf( "i= %d, depth= %d\n", i, depth ) )
    if( depth < 10 ) testfun( depth + 1 )
  }
})

This very neatly wraps the testfun function in a local environment which holds i. This method should be acceptable in packages submitted CRAN, whereas modifying the global environment is not.

How can I write a recursive function in R?

Calling recursive functions in R

There might be a data.table/dplyr solution out there, but this one is pretty simple.

# Just paste together the values of the column you want to aggregate over.
# This creates a vector of factors
f <- function(data, v) {apply(data[,v,drop=F], 1, paste, collapse = ".")}

# Aggregate, tapply, ave, and a few more functions can do the same thing
by(data = df,                                   # Your data here
   INDICES = f(df, c("group", "wk", "source")), # Your data and columns here
   FUN = identity, simplify = F)                # Your function here

Can also use library(dplyr) and library(data.table)

df %>% data.table %>% group_by(group, wk, source) %>% do(yourfunctionhere, use . for x)

What functions in R can recursively reduce the rows of a dataframe?

Reduce by itself isn't going to operate row-wise like you want: it works well on a simple vector or list, but not on rows of a frame.

Try this frame-aware function:

Reduce_frame <- function(data, expr, init) {
  expr <- substitute(expr)
  out <- rep(init[1][NA], nrow(data))
  for (rn in seq_len(nrow(data))) {
    out[rn] <- init <- eval(expr, envir = data[rn,])
  }
  out
}

Reduce_frame(purchases, init + quantity*price, init=0)
# [1] 150 290 390 432 594

Application of a recursive function within a dplyr context in R

I think you can probably get what you need here with a mix of tidyr::fill to fill NA values from above, combined with cumprod to get the cumulative effect of multiplying by the coefficient, and ifelse to choose when to use it. There's also a "working" column named V which is created and destroyed in the process.

library(dplyr)

df %>% 
  mutate(V = tidyr::fill(df, VALUE)$VALUE) %>% 
  group_by(ID) %>% 
  mutate(VALUE = ifelse(is.na(VALUE), 
                        V * cumprod(ifelse(is.na(VALUE), COEFF, 1)), 
                        VALUE)) %>% select(-V)
#> # A tibble: 10 x 3
#> # Groups:   ID [2]
#>    ID    VALUE COEFF
#>    <fct> <dbl> <dbl>
#>  1 a       1     1  
#>  2 a       3     2  
#>  3 a       3     1  
#>  4 a       1.5   0.5
#>  5 a     150   100  
#>  6 b       2     1  
#>  7 b       2     1  
#>  8 b       3     1  
#>  9 b       3     1  
#> 10 b       3     1

^{Created on 2020-06-30 by the reprex package (v0.3.0)}

How to apply a custom recursive function with data.table and loop over each index group-wise?

Does this use of Reduce do the trick?

tmp = data.table(
  grp = c(rep(0,6), rep(1,6)),
  x=c(10,20,30,40,50,60,1,2,3,4,5,6),
  y=c(1,2,3,4,5,6, 10,20,30,40,50,60)
)
tmp[, z:=Reduce(f=function(z,i) z + x[i-1] - y[i-1],
                x=(1:.N)[-1],
                init=0,
                accumulate = T)
    ,by=grp
]

Output:

    grp  x  y    z
 1:   0 10  1    0
 2:   0 20  2    9
 3:   0 30  3   27
 4:   0 40  4   54
 5:   0 50  5   90
 6:   0 60  6  135
 7:   1  1 10    0
 8:   1  2 20   -9
 9:   1  3 30  -27
10:   1  4 40  -54
11:   1  5 50  -90
12:   1  6 60 -135

Take for example, row 4. The value in the z column is 54, which is equal to the prior row's z-value + prior row's x-value, minus prior row's y-value.

The function f within Reduce can take any complicated form, including ifelse statements. Here is an example, where I've made a function called func, which is a wrapper around Reduce. Notice that within the Reduce statement, f is a function taking prev (thanks to suggestion by @r2evans), and this function first calculates previous row's s value minus previous row's t value (this is akin to your x[-1]-y[-1]. Then there is an ifelse statement. If the difference between the prior rows s and t value (i.e. k) is >20, then the new value in this row will be the previous z value minus the product of 20-4k (i.e. prev-(20-4k)), otherwise it will the previous z value + k (i.e. which is equal to your original formulation: z[i-1]+x[i-1]-y[i-1])

func <- function(s,t) {
  Reduce(
    f=function(prev,i) {
      k=s[i-1] - t[i-1]
      ifelse(k>10, prev -(20-4*k), prev+k)
    },
    x=2:length(s),
    init=0,
    accumulate = TRUE
  )
}

You can then assign the value of the func(x,y) to z, like this:

tmp[, z:=func(x,y), by=.(grp)][]

Output:

    grp  x  y    z
 1:   0 10  1    0
 2:   0 20  2    9
 3:   0 30  3   61
 4:   0 40  4  149
 5:   0 50  5  273
 6:   0 60  6  433
 7:   1  1 10    0
 8:   1  2 20   -9
 9:   1  3 30  -27
10:   1  4 40  -54
11:   1  5 50  -90
12:   1  6 60 -135

Are Recursive Functions Used in R