Introduction to Recursion

(Textbook: Section 16.1)

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"

Problem with Fibonacci Function

Recall the Fibonacci Function

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

fib(10)

[1] 55

Seems to work just fine.

But …

Try:

fib(30)

Takes a scary long time to finish.

Don’t even bother with:

fib(50)

Diagnosis

The number of recalls that fib() must make grows exponentially with the size of n.

Let’s investigate this:

counter <- 0
fib2 <- function(n) {
  counter <<- counter + 1
  if (n %in% c(1, 2)) {
    return(1)
  }
  Recall(n - 1) + Recall(n - 2)
}
fib2(10)

[1] 55

counter

[1] 109

Further Investigation

## highest fib number to find:
m <- 25
## set up some results vectors:
calls <- numeric(m)
fibs <- numeric(m)
for (i in 1:m) {
  counter <- 0
  fibs[i] <- fib2(i)
  calls[i] <- counter
}

calls - (fibs + fibs - 1)

 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Math Fact: the number of calls made by the fib() function when finding the nth Fibonacci number is:

\[2 \times F_n - 1.\]