Rekursive Funktionen

Teil des Abschnitts Logik und Ablaufsteuerung der R-Journey von Coddy. Lektion 50 von 64.

Eine rekursive Funktion ruft sich selbst mit einer kleineren Version des Problems auf. Sie benötigt einen Basisfall, der zurückkehrt, ohne sich selbst aufzurufen, sonst würde sie niemals anhalten:

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

Ausgabe:

[1] 120

Jeder Aufruf wartet darauf, dass der kleinere Aufruf abgeschlossen wird: fact(3) berechnet 3 * fact(2), was 2 * fact(1) berechnet, das 1 zurückgibt. Jeder Schritt muss sich auf den Basisfall zubewegen:

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

Ausgabe:

3 2 1 go

Rekursion eignet sich für Daten, die kleinere Kopien ihrer selbst enthalten, etwa eine Liste, die Listen enthält. Diese Funktion addiert jede Zahl, unabhängig davon, wie tief sie verschachtelt ist:

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

Ausgabe:

[1] 15

Ein rekursiver Aufruf kann das Problem ebenfalls in zwei Hälften teilen. Die binäre Suche betrachtet die Mitte eines sortierten Vektors und fährt mit der Hälfte fort, die das Ziel enthalten kann:

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

Ausgabe:

[1] 4
[1] NA

Aufgabe

Einfach

Vervollständige count_digits(n) rekursiv. Eine Zahl unter 10 hat 1 Ziffer; jede größere Zahl hat eine Ziffer mehr als n %/% 10. Wandle die Zahl nicht in Text um.

Der bereitgestellte Code liest eine ganze Zahl n (0 oder größer) ein und gibt den zurückgegebenen Wert aus.

Probier es selbst

count_digits <- function(n) {
  # Schreibe deinen Code hier
  0
}

# Bereitgestellter Ein-/Ausgabe-Code: belasse ihn wie er ist
input <- suppressWarnings(readLines(file("stdin")))
cat(count_digits(as.numeric(input[1])), sep = "\n")