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

ints <- function(start, end) {
  
  if (start >= end) return(start)    # Exit clause
  
  result <- rec_ints(start+1, end)   # Call to self
  
  return(c(start, result))           # Return statement
  
}

ints(3, 12)

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

Calculate the power \(a^b\)

pow(3, 7)

## [1] 2187

Sequential: \[3*3*3*3*3*3*3\]

Recursive: \[(3*(3*(3*(3*(3*(3*3))))))\]

Programming:

times(3, times(3, times(3, times(3, times(3, times(3, 3)))))

So let's program it!

• Exit clause (!!!)
• Call to self
• Return statement

Calculate the power \(a^b\)

pow(3, 7)

## [1] 2187

Hint: exit statement

if (b == 1) return(a)

rec_pow <- function(a, b) {
  
  if (b == 1) return(a)            # Exit clause
  
  result <- a * rec_pow(a, b - 1)  # Call to self
  
  return(result)                   # Return statement
  
}

rec_pow(3, 7)

## [1] 2187

List / tree traversion is a classic scenario for recursive functions.

Example: get the 1 elements from the the following list:

li <- list(1,list(0,list(1,2,3),list(1,3,2),1),list(2,3),list(4,3,2,1))

traverse <- function(el) {
  if (identical(el, 1)) return(1) 
  
  if (is.list(el)) {
    result <- c()
    for (i in 1:length(el))
      result <- c(result, traverse(el[[i]]))
    return(result)
  }
  
  # implicit exit clause: else do nothing / return NULL
}

traverse(li)

## [1] 1 1 1 1 1

Euclid's algorithm (300 B.C.) for finding the greatest common divisor

\[gcd(8, 12) = 4\]

\[gcd(12, 36) = 12\]

gcd <- function(a, b) if (b==0) a else gcd(b, a%%b)

gcd(88, 2662)

## [1] 22

• A function that outputs the \(n^{th}\) fibonacci number fib(10) = 55
• A function that outputs the length of a string len("hoihoi") = 6
• A function that counts the number of end nodes in a nested list end(list(list(1), list(list(1), 2))) = 3

Pick one!

# nth fibonacci number
fib <- function(n) if (n <= 2) 1 else fib(n-1) + fib(n-2)

fib(10)

## [1] 55

# string count
len <- function(string) if (string == "") 0 else 1 + len(substring(string, 2))

len("hoihoi")

## [1] 6

# end
end <- function(li) if (is.list(li)) sum(sapply(li, end)) else 1

end(list(list(1), list(list(1), 2)))

## [1] 3