Introduction to Recursion

(Textbook: ——)

What is a Recursive Function?

Recursive Function

A recursive function is a function that contains a call to itself in its own body.

Example: Counting Down

countdown <- function(n) {
  ## Base case:
  if (n == 0) return(cat("Blastoff!"))
  ## Recursive case:
  cat(n, ", ...\n", sep = "")
  Recall(n - 1)
}

Try It Out

countdown(5)

5, ...
4, ...
3, ...
2, ...
1, ...
Blastoff!

Example: Handshakes

\(n\) people are in a room. Each person shakes the hand of each other person. How many handshakes are there?

handshakes <- function(n) {
  ## Base case:
  if (n == 1) {
    return(0)
  }
  ## Recursive case:
  n - 1 + Recall(n - 1)
}

Try It Out

handshakes(4)

[1] 6

Example: Fibonacci Sequence

The Fibonacci numbers are defined as follows:

• \(F_1 = 1\)
• \(F_2 = 1\)
• For all \(n \geq 3\), \(F_n = F_{n-1} + F_{n-2}\)

Can we write a function to compute the \(n\)-th Fibonacci number, for any \(n \geq 1\)?

Fibonacci Function

fib <- function(n) {
  ## Base cases:
  if (n %in% c(1, 2)) {
    return(1)
  }
  ## Recursive case:
  Recall(n - 1) + Recall(n - 2)
}

Try It Out

fib(9)

[1] 34

Example: Conversion to Base

Recall conversion to any desired base:

to_base <- function(b, n) {
  if (b > 36) stop("choose a lower base")
  digits <- c(0:9, letters)[1:b]
  numeral <- ""
  curr <- n
  while (curr >= b) {
    quot <- curr %/% b
    rem <- curr %% b
    numeral <- str_c(digits[rem + 1], numeral, sep = "")
    curr <- quot
  }
  str_c(digits[curr + 1], numeral, sep = "")
}

to_base(7, 5463)

[1] "21633"

Rewrite as Recursive

to_base_rec <- function(b, n) {
  if (b > 36) stop("choose a lower base")
  digits <- c(0:9, letters)[1:b]
  ## base case
  if (n < b) return(digits[n + 1])
  ## recursive case:
  quot <- n %/% b
  rem <- n %% b
  str_c(Recall(b, quot), digits[rem + 1], sep = "")
}

to_base_rec(7, 5463)

[1] "21633"