Fonctions récursives

Une fonction récursive s’appelle elle-même sur une version plus petite du problème. Elle a besoin d’un cas de base qui retourne une valeur sans s’appeler elle-même, sinon elle ne s’arrêterait jamais :

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

Sortie :

[1] 120

Chaque appel attend que l’appel plus petit soit terminé : fact(3) calcule 3 * fact(2), qui calcule 2 * fact(1), lequel renvoie 1. Chaque étape doit progresser vers le cas de base :

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

Sortie :

3 2 1 go

La récursion convient aux données qui contiennent de plus petites copies d’elles-mêmes, comme une liste qui contient des listes. Cette fonction additionne chaque nombre, quelle que soit la profondeur à laquelle il est imbriqué :

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

Sortie :

[1] 15

Un appel récursif peut également diviser le problème en deux. La recherche binaire examine le milieu d’un vecteur trié et continue dans la moitié qui peut contenir la cible :

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

Sortie :

[1] 4
[1] NA