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

Note on Recall()

Recursive functions are often written to call themselves using their own names:

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

This works, but it can be dangerous. Why?

Illustrative App

To see the countdown and Fibonacci functions (plus some other recursive functions) at work in an interactive way, consult this app.

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

investigate_calls <- function(n) {
  counter <- 0
  fib2 <- function(n) {
  counter <<- counter + 1
  if (n %in% c(1, 2)) {
    return(1)
  }
  Recall(n - 1) + Recall(n - 2)
}
  fib_number <- fib2(n = n)
  cat("The number of calls to compute fib(", n, ") was ", counter, ".\n", sep = "")
  cat("2 * fib(", n, ") - 1 equals ", 2 * fib_number - 1, ".\n", sep = "")
}

Try It!

Math Fact

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

\[2 \times F_n - 1.\]