Récursion dans R

Une fois un doctorant en mathématiques que je savais très brillant, mais qui avait peu d'expérience en programmation, je cherchais mes conseils sur la façon d'écrire une certaine fonction. J'ai rapidement dit: «Vous n'avez même pas besoin de me dire ce que la fonction est censée faire. La réponse est d'utiliser la récursivité. "Surpris, il a demandé quelle est la récursivité. Je lui ai conseillé de lire sur le célèbre problème des tours de Hanoi. Effectivement, il est revenu le lendemain, rapportant qu'il était capable de résoudre son problème en quelques lignes de code, en utilisant la récursivité. Évidemment, la récursivité peut être un outil puissant. Eh bien, qu'est-ce que c'est?
Une fonction récursive s'appelle elle-même. Si vous n'avez pas rencontré ce concept auparavant, cela peut sembler étrange, mais l'idée est en fait simple. En termes approximatifs, l'idée est la suivante:
Pour résoudre un problème de type X en écrivant une fonction récursive f ():
1. Cassez le problème initial de type X en un ou plusieurs problèmes plus petits de type X.
2. Dans f (), appelez f () sur chacun des petits problèmes.
3. Dans f (), rassembler les résultats de (b) pour résoudre le problème originel.

1 Une mise en œuvre rapide
Un exemple classique est Quicksort, un algorithme utilisé pour trier un vecteur de nombres allant du plus petit au plus grand. Par exemple, supposons que nous souhaitions trier le vec¬tor (5,4,12,13,3,8,88). Nous comparons tout d'abord au premier élément 5 pour former deux sous-vecteurs: l'un composé des éléments inférieurs à 5 et l'autre constitué des éléments supérieurs ou égaux à 5. Cela nous donne des sous-vecteurs (4, 3) et (12 , 13,8,88). Nous appelons alors la fonction sur les sous-récepteurs, en retournant (3,4) et (8,12,13,88). Nous les stringons ensemble avec le 5, cédant (3,4,5,8,12,13,88), comme désiré.
La fonction de filtrage vectoriel de R et sa fonction c () facilitent l'implémentation de Quicksort.
NOTE Cet exemple est destiné à démontrer la récursivité. La propre fonction de tri de R, sort (), est beaucoup plus rapide, comme il est écrit en C.

qs <- function(x) {
if (length(x) <= 1) return(x)
pivot <- x[1]
therest <- x[-1]
sv1 <- therest[therest < pivot]
sv2 <- therest[therest >= pivot]
sv1 <- qs(sv1)
sv2 <- qs(sv2)
return(c(sv1,pivot,sv2))
}

qs <- function(x) {
if (length(x) <= 1) return(x)
pivot <- x[1]
therest <- x[-1]
sv1 <- therest[therest < pivot]
sv2 <- therest[therest >= pivot]
sv1 <- qs(sv1)
sv2 <- qs(sv2)
return(c(sv1,pivot,sv2))
}

Notez attentivement la condition de terminaison:

if (length(x) <= 1) return(x)

if (length(x) <= 1) return(x)

Sans cela, la fonction continuerait à s'appeler à plusieurs reprises sur des vecteurs vides, exécutant pour toujours. (En fait, l'interprète R refuserait éventuellement d'aller plus loin, mais vous avez l'idée.)
Ça a l'air magique? La récursivité est certainement une façon élégante de résoudre de nombreux problèmes. Mais la récursion a deux inconvénients potentiels:
• C'est assez abstrait. Je savais que l'étudiant diplômé, en tant que mathématicien, prendrait à la récursion comme un poisson à l'eau, parce que la récurrence est vraiment l'inverse de la preuve par l'induction mathématique. Mais de nombreux programmeurs le trouvent difficile.
• La récursivité est très somptueuse dans son utilisation de la mémoire, ce qui peut poser problème dans R si elle est appliquée à de gros problèmes.

Récursion dans R

Enquête statistique

A qui nos services?