Funzioni ricorsive

Una funzione ricorsiva richiama sé stessa su una versione più semplice del problema. Ha bisogno di un caso base che restituisca un valore senza richiamare sé stessa, altrimenti non si fermerebbe mai:

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

Output:

[1] 120

Ogni chiamata attende che quella più piccola finisca: fact(3) calcola 3 * fact(2), che calcola 2 * fact(1), che restituisce 1. Ogni passaggio deve avvicinarsi al caso base:

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

La ricorsione è adatta a dati che contengono copie più piccole di sé stessi, come una lista che contiene altre liste. Questa funzione somma ogni numero, a qualsiasi profondità sia annidato:

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

Una chiamata ricorsiva può anche dividere il problema a metà. La ricerca binaria esamina l’elemento centrale di un vettore ordinato e prosegue nella metà che può contenere il valore cercato:

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