Hàm đệ quy

Thuộc phần Logic và luồng điều khiển trong hành trình R của Coddy. Bài học 50 trên 64.

Hàm đệ quy (recursive) gọi chính nó với một phiên bản nhỏ hơn của bài toán. Hàm cần có trường hợp cơ sở (base case) trả về mà không gọi chính nó, nếu không hàm sẽ không bao giờ dừng:

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

Đầu ra:

[1] 120

Mỗi lần gọi đều chờ lần gọi nhỏ hơn hoàn tất: fact(3) tính 3 * fact(2), biểu thức này tính 2 * fact(1), rồi trả về 1. Mỗi bước phải tiến gần hơn đến trường hợp cơ sở:

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

Đầu ra:

3 2 1 go

Đệ quy phù hợp với dữ liệu có chứa những bản sao nhỏ hơn của chính nó, chẳng hạn như danh sách chứa các danh sách. Hàm này cộng mọi số, dù chúng lồng sâu đến đâu:

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

Đầu ra:

[1] 15

Lời gọi đệ quy cũng có thể chia bài toán thành hai nửa. Tìm kiếm nhị phân kiểm tra phần tử ở giữa của một vector đã sắp xếp rồi tiếp tục ở nửa có thể chứa giá trị cần tìm:

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

Đầu ra:

[1] 4
[1] NA

Thử thách

Dễ

Hoàn thành count_digits(n) bằng đệ quy. Một số nhỏ hơn 10 có 1 chữ số; mọi số lớn hơn có số chữ số nhiều hơn n %/% 10 một chữ số. Đừng chuyển số thành văn bản.

Đoạn code được cung cấp đọc một số nguyên n (0 trở lên) và in ra giá trị trả về.

Tự làm thử

count_digits <- function(n) {
  # Viết code của bạn ở đây
  0
}

# Đoạn code đầu vào/đầu ra có sẵn: giữ nguyên
input <- suppressWarnings(readLines(file("stdin")))
cat(count_digits(as.numeric(input[1])), sep = "\n")