Recursive Functions

Part of the Logic & Flow section of Coddy's R journey. Lesson 50 of 64.

A recursive function calls itself on a smaller version of the problem. It needs a base case that returns without calling itself, or it would never stop:

fact <- function(n) {
  if (n <= 1) return(1)
  n * fact(n - 1)
}
print(fact(5))

Output:

[1] 120

Each call waits for the smaller call to finish: fact(3) computes 3 * fact(2), which computes 2 * fact(1), which returns 1. Every step must move toward the base case:

count_down <- function(n) {
  if (n == 0) {
    cat("go\n")
    return(invisible(NULL))
  }
  cat(n, "")
  count_down(n - 1)
}
count_down(3)

Output:

3 2 1 go

Recursion fits data that contains smaller copies of itself, such as a list that holds lists. This function adds every number however deep it is nested:

deep_sum <- function(x) {
  if (is.numeric(x)) return(sum(x))
  total <- 0
  for (item in x) total <- total + deep_sum(item)
  total
}
print(deep_sum(list(1, list(2, 3), list(list(4)), 5)))

Output:

[1] 15

A recursive call can also split the problem in half. Binary search looks at the middle of a sorted vector and continues in the half that can hold the target:

find <- function(v, target, lo = 1, hi = length(v)) {
  if (lo > hi) return(NA)
  mid <- (lo + hi) %/% 2
  if (v[mid] == target) return(mid)
  if (v[mid] < target) find(v, target, mid + 1, hi) else find(v, target, lo, mid - 1)
}
print(find(c(2, 5, 8, 12, 19), 12))
print(find(c(2, 5, 8, 12, 19), 7))

Output:

[1] 4
[1] NA

Challenge

Easy

Complete count_digits(n) recursively. A number below 10 has 1 digit; any larger number has one more digit than n %/% 10. Do not convert the number to text.

The supplied code reads a whole number n (0 or more) and prints the returned value.

Try it yourself

count_digits <- function(n) {
  # Write your code here
  0
}

# Supplied input/output code: keep it as it is
input <- suppressWarnings(readLines(file("stdin")))
cat(count_digits(as.numeric(input[1])), sep = "\n")