Fungsi Rekursif

Termasuk bagian Logika dan Alur dalam perjalanan R di Coddy. Pelajaran 50 dari 64.

Fungsi rekursif memanggil dirinya sendiri untuk versi masalah yang lebih kecil. Fungsi ini memerlukan kasus dasar yang mengembalikan nilai tanpa memanggil dirinya sendiri, atau fungsi tersebut tidak akan pernah berhenti:

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

Output:

[1] 120

Setiap pemanggilan menunggu pemanggilan yang lebih kecil selesai: fact(3) menghitung 3 * fact(2), yang menghitung 2 * fact(1), yang mengembalikan 1. Setiap langkah harus bergerak menuju kasus dasar:

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

Rekursi cocok untuk data yang berisi salinan dirinya yang lebih kecil, seperti list yang menyimpan list. Fungsi ini menjumlahkan setiap angka, sedalam apa pun tingkat penyarangannya:

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

Pemanggilan rekursif juga dapat membagi masalah menjadi dua bagian. Pencarian biner memeriksa bagian tengah dari vektor yang sudah diurutkan, lalu melanjutkan pencarian di bagian yang dapat memuat 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

Tantangan

Mudah

Lengkapi count_digits(n) secara rekursif. Bilangan di bawah 10 memiliki 1 digit; bilangan yang lebih besar memiliki satu digit lebih banyak daripada n %/% 10. Jangan ubah bilangan menjadi teks.

Code yang disediakan membaca bilangan bulat n (0 atau lebih) dan mencetak nilai yang dikembalikan.

Coba sendiri

count_digits <- function(n) {
  # Tulis kodemu di sini
  0
}

# Kode input/output yang disediakan: biarkan apa adanya
input <- suppressWarnings(readLines(file("stdin")))
cat(count_digits(as.numeric(input[1])), sep = "\n")