A recursive function is a function that calls itself.

Sequentially:

\[ x! = \prod_{i=1}^x x\]

Recursively:

\[ x! = x \cdot (x-1)! \] \[ 1! = 1 \]

Sequentially:

fac <- function(x) {
  out <- 1
  for (i in 1:x) {
    out <- out * i
  }
  return(out)
}

Recursively:

fac <- function(x) {
  if (x == 1) return(1)
  return(x * fac(x - 1))
}

• exit clause (!!!)
• call to self
• return statement

fac <- function(x) {
  
  if (x == 1) return(1)     # exit clause
  
  result <- x * fac(x - 1)  # call to self
  
  return(result)            # return statement
  
}

• See some cool algorithms
• Try out recursive programming
  
  

Get your laptops out & start RStudio

Warming-up: generate a sequence of integers.

Goal:

ints(3, 12)

##  [1]  3  4  5  6  7  8  9 10 11 12

Not allowed:

3:12, seq(3, 12, 1), seq_along(sth), etcetera

Try it out!

My sequential solution

ints <- function(start, end) {
  result <- round(start)
  while (result[length(result)] < end) {
    result <- c(result, result[length(result)] + 1)
  }
  return(result)
}

ints(3, 12)

##  [1]  3  4  5  6  7  8  9 10 11 12

Here is a recursive solution:

rec_ints <- function(start, end) {
  if (start <= end) c(start, rec_ints(start+1, end))
}

rec_ints(3, 12)

##  [1]  3  4  5  6  7  8  9 10 11 12

!! MAGIC !!