21/06/2018





A recursive function is a function that calls itself.

Computing a factorial: math

Sequentially:

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

Recursively:

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

Computing a factorial: programming

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))
}

Three elements of a recursive function

  • 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
  
}

What else are we going to do

  • See some cool algorithms
  • Try out recursive programming

Get your laptops out & start RStudio

Practical

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!

Practical

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

Practical

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 !!

Three elements of a recursive function