递归函数

本课属于 Coddy R 学习旅程的“逻辑与流程”单元。第 50 课，共 64 课。

递归函数会针对问题的更小版本调用自身。它需要一个基准情况，在不调用自身的情况下返回，否则它将永远不会停止：

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

输出：

[1] 120

每次调用都会等待更小的调用完成：fact(3) 计算 3 * fact(2)，后者计算 2 * fact(1)，而 fact(1) 返回 1。每一步都必须朝着基本情况推进：

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

输出：

3 2 1 go

递归适用于包含自身较小副本的数据，例如包含列表的列表。这个函数会累加所有数字，无论它们嵌套得多深：

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

输出：

[1] 15

递归调用也可以把问题分成两半。二分查找会查看已排序向量的中间位置，并继续在可能包含目标值的那一半中查找：

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

输出：

[1] 4
[1] NA

挑战

简单

用递归完成 count_digits(n)。小于 10 的数字有 1 位；任何更大的数字都比 n %/% 10 多一位。不要把数字转换成文本。

提供的代码会读取一个整数 n（0 或更大），并打印返回值。

亲手试试

count_digits <- function(n) {
  # 在这里编写你的代码
  0
}

# 已提供的输入和输出代码：保持原样
input <- suppressWarnings(readLines(file("stdin")))
cat(count_digits(as.numeric(input[1])), sep = "\n")