Une fois un étudiant en mathématiques dont je savais être très clair, mais qui
Avait peu de fond de programmation, cherché mes conseils sur la façon d'écrire un certain
fonction. J'ai rapidement dit: "Vous n'avez même pas besoin de me dire quelle est la fonction
Est supposé faire. La réponse est d'utiliser la récurrence. "Surligné, il a demandé
Quelle récurrence est. Je lui ai conseillé de lire les célèbres tours de Hanoi
problème. Bien sûr, il est retourné le lendemain, déclarant qu'il était capable
Pour résoudre son problème dans 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 gros, le
L'idée est la suivante:
Pour résoudre un problème de type X en écrivant une fonction récursive f ():
1. Casser le problème original du type X en un ou plusieurs plus petit
Problèmes de type X.
2. Dans f (), appelez f () sur chacun des problèmes plus petits.
3. Dans f (), rassembler les résultats de (b) pour résoudre l'original
problème.

7.9.1 Une implémentation Quicksort
Un exemple classique est Quicksort, un algorithme utilisé pour trier un vecteur de nombres
Du plus petit au plus grand. Par exemple, supposons que nous souhaitons trier le vecteur
(5,4,12,13,3,8,88). Nous comparons d'abord tout au premier élément, 5,
Pour former deux sous-vecteurs: l'un constitué par les éléments inférieurs à 5 et le
Autre composé des éléments supérieurs ou égaux à 5. Cela nous donne
Sous-secteurs (4,3) et (12,13,8,88). Nous appelons ensuite la fonction sur les sous-secteurs,
Retour (3,4) et (8,12,13,88). Nous agissons avec les 5,
Cédant (3,4,5,8,12,13,88), comme désiré.
La capacité de filtrage vectoriel de R et sa fonction c () rendent la mise en œuvre
De Quicksort assez facile.
REMARQUE Cet exemple est destiné à démontrer la récursivité. La propre fonction de tri de R,
Sort (), est beaucoup plus rapide, car il est écrit en C.
Qs <- function (x) {
Si (longueur (x) <= 1) retour (x)
Pivot <- x [1]
Therest <- x [-1]
Sv1 <- therest [therest <pivot]
Sv2 <- therest [therest> = pivot]
Sv1 <- qs (sv1)
Sv2 <- qs (sv2)
Retour (c (sv1, pivot, sv2))
}
176 Chapitre 7
Www.it

Notez soigneusement la condition de terminaison:
Si (longueur (x) <= 1) retour (x)
Sans cela, la fonction continuerait à se répéter à plusieurs reprises sur vide
Vecteurs, exécutant pour toujours. (En fait, l'interprète R finirait
Refuse d'aller plus loin, mais vous avez l'idée.)
Ca ressemble à de la magie? La récurrence est certainement une façon élégante de résoudre beaucoup
problèmes. Mais la récurrence présente deux inconvénients potentiels:
• C'est assez abstrait. Je savais que l'étudiant diplômé, en tant que bon mathématicien,
Prendrait la récurrence comme un poisson à l'eau, car la récurrence est
Vraiment l'inverse de la preuve par induction mathématique. Mais beaucoup
Les programmeurs le trouvent difficile.
• La récurrence est très somptueuse dans son utilisation de la mémoire, ce qui peut être un problème dans R
Si appliqué à de gros problèmes.

7.9.2 Exemple étendu: un arbre de recherche binaire
Les structures de données de Treelike sont communes en informatique et en statistiques.
Dans R, par exemple, la bibliothèque Rpart pour une approche de parution récursive
À la régression et à la classification est très populaire. Les arbres ont évidemment des applications
En généalogie, et plus généralement, les graphiques constituent la base de l'analyse de
réseaux sociaux.
Cependant, il existe de véritables problèmes avec les structures arborescentes dans R, dont beaucoup sont liés
Au fait que R n'a pas de références de style pointeur, comme indiqué dans
Section 7.7. En effet, pour cette raison et pour la performance, un meilleur
L'option consiste souvent à écrire le code central en C avec un enroulage R, comme nous allons en discuter
Au chapitre 15. Pourtant, les arbres peuvent être implémentés dans le R lui-même, et si la performance
N'est pas un problème, l'utilisation de cette approche peut être plus pratique.
Par souci de simplicité, notre exemple ici sera un arbre de recherche binaire,
Une structure de données informatique classique qui possède la propriété suivante:
Dans chaque noeud de l'arbre, la valeur sur le lien gauche, le cas échéant, est inférieure
Ou égal à celui du parent, alors que la valeur à droite
Le lien, le cas échéant, est supérieur à celui du parent.
Voici un exemple:
8
5 20
2 6
Nous avons stocké 8 dans la racine, c'est-à-dire la tête de l'arbre. Ses deux enfants
Les noeuds contiennent 5 et 20, et le premier possède deux noeuds enfants, qui
Magasin 2 et 6.
Notez que la nature des arbres de recherche binaires implique que sur n'importe quel noeud,
Tous les éléments de la sous-arborescence gauche du nœud sont inférieurs ou égaux à
Valeur stockée dans ce nœud, tandis que le sous-arbre approprié stocke les éléments qui
Sont supérieurs à la valeur dans ce mode. Dans notre arbre d'exemples, où la racine
Le noeud contient 8, toutes les valeurs dans le sous-arbre gauche-5, 2 et 6-sont moins
De 8, tandis que 20 est supérieur à 8.
Si implémenté en C, un nœud d'arbre serait représenté par une structure C,
Similaire à une liste R, dont le contenu est la valeur mémorisée, un pointeur vers la gauche
Enfant, et un pointeur vers l'enfant droit. Mais puisque R manque de variables de pointeur,
Que pouvons-nous faire?
Notre solution est de revenir aux bases. Dans les anciens jours prépoints
Dans FORTRAN, des structures de données liées ont été implémentées dans de longs tableaux. UNE
Pointeur, qui dans C est une adresse de mémoire, était plutôt un index de tableau.
Plus précisément, nous représenterons chaque noeud par une ligne dans une matrice à trois colonnes.
La valeur mémorisée du nœud sera dans le troisième élément de cette ligne, alors que
Les premier et deuxième éléments seront les liens gauche et droit. Par exemple,
Si le premier élément d'une ligne est 29, cela signifie que le lien gauche de ce noeud pointe vers
Le noeud mémorisé dans la rangée 29 de la matrice.
N'oubliez pas que l'allocation d'espace pour une matrice dans R est longue
activité. Dans un effort pour amortir le temps de répartition de la mémoire, nous allouons de nouveaux
Espace pour une matrice d'arbres plusieurs lignes à la fois, au lieu d'une rangée par rangée. le
Le nombre de lignes attribuées chaque fois sera donné dans la variable inc. Comme si
Commun avec la traversée d'arbres, nous mettons en œuvre notre algorithme avec récursion.
REMARQUE Si vous prévoyez que la matrice deviendra assez importante, vous voudrez peut-être doubler sa
Taille à chaque allocation, plutôt que de la pousser linéairement comme nous l'avons fait ici. Cela permettrait
Réduisez le nombre de perturbations longues.
Avant de discuter du code, passons par une session rapide d'arbre
Construire en utilisant ses routines.
> X <- newtree (8,3)
> X
$ Mat
[, 1] [, 2] [, 3]
[1,] NA NA 8
[2,] NA NA NA
[3,] NA NA NA
$ Nxt
[1] 2
$ Inc
[1] 3
> X <- ins (1, x, 5)
> X
$ Mat
[, 1] [, 2] [, 3]
[1,] 2 NA 8
[2,] NA NA 5
[3,] NA NA NA
$ Nxt
[1] 3
$ Inc
[1] 3
> X <- ins (1, x, 6)
> X
$ Mat
[, 1] [, 2] [, 3]
[1,] 2 NA 8
[2,] NA 3 5
[3,] NA NA 6
$ Nxt
[1] 4
$ Inc
[1] 3
> X <- ins (1, x, 2)
> X
$ Mat
[, 1] [, 2] [, 3]
[1,] 2 NA 8
[2,] 4 3 5
[3,] NA NA 6
[4,] NA NA 2
[5,] NA NA NA
[6,] NA NA NA
$ Nxt
[1] 5
$ Inc
[1] 3
> X <- ins (1, x, 20)
> X
$ Mat
[, 1] [, 2] [, 3]
R

[1,] 2 5 8
[2,] 4 3 5
[3,] NA NA 6
[4,] NA NA 2
[5,] NA NA 20
[6,] NA NA NA
$ Nxt
[1] 6
$ Inc
[1] 3
Que s'est-il passé ici? Tout d'abord, la commande contenant notre appel
Newtree (8,3) crée un nouvel arbre, assigné à x, stockant le numéro 8. Le
L'argument 3 spécifie que nous allouons trois rangées de stockage à la fois.
Le résultat est que le composant matriciel de la liste x est maintenant le suivant:
[, 1] [, 2] [, 3]
[1,] NA NA 8
[2,] NA NA NA
[3,] NA NA NA
Trois rangées de stockage sont effectivement attribuées, et nos données sont maintenant constituées
Juste du nombre 8. Les deux valeurs de NA dans cette première rangée indiquent que ceci
Le noeud de l'arbre n'a actuellement aucun enfant.
Nous faisons ensuite appel ins (1, x, 5) pour insérer une seconde valeur, 5, dans la
Arbre x. L'argument 1 spécifie la racine. En d'autres termes, l'appel dit:
"Insérer 5 dans le sous-arbre de x dont la racine est dans la rangée 1." Notez que nous devons
Réaffectez la valeur de retour de cet appel à x. Encore une fois, cela est dû au manque
Des variables de pointeur dans R. La matrice ressemble maintenant à ceci:
[, 1] [, 2] [, 3]
[1,] 2 NA 8
[2,] NA NA 5
[3,] NA NA NA
L'élément 2 signifie que la liaison gauche hors du noeud contenant 8 est
Destiné à pointer vers la rangée 2, où notre nouvel élément 5 est stocké.
La session se poursuit de cette manière. Notez que lorsque notre allocation initiale
De trois lignes est plein, ins () affecte trois nouvelles lignes, pour un total de six. Dans
La fin, la matrice est la suivante:
[, 1] [, 2] [, 3]
[1,] 2 5 8
[2,] 4 3 5
[3,] NA NA 6
[4,] NA NA 2
[5,] NA NA 20
[6,] NA NA NA
Cela représente l'arbre que nous avons représenté pour cet exemple.
Le code suit. Notez qu'il ne comprend que des routines pour insérer de nouveaux éléments
Et traverser l'arbre. Le code pour supprimer un nœud est un peu plus
Complexe, mais il suit un modèle similaire.
1 # routines pour créer des arbres et insérer des éléments dans eux sont inclus
2 ci-dessous; Une routine de suppression est laissée au lecteur en tant qu'exercice
3
Le stockage 4 # est dans une matrice, disons m, une ligne par nœud de l'arbre; Si la rangée
5 # i contient (u, v, w), puis le nœud i stocke la valeur w et est parti et
6 # liens droits vers les lignes u et v; Les liens nuls ont la valeur NA
7
8 # l'arbre est représenté comme une liste (mat, nxt, inc), où mat est le
9 # matrix, nxt est la prochaine ligne vide à utiliser, et inc est le nombre de
10 # rangées d'extension à allouer chaque fois que la matrice devient pleine
11
12 # imprimer l'arbre trié via la traversée dans l'ordre
13 printtree <- function (hdidx, tr) {
14 gauche <- tr $ mat [hdidx, 1]
15 si (! Is.na (gauche)) printtree (gauche, tr)
16 imprimer (tr $ mat [hdidx, 3]) # imprimer la racine
17 droite <- tr $ mat [hdidx, 2]
18 si (! Is.na (droite)) printtree (droite, tr)
19}
20
21 # initialise une matrice de stockage, avec la valeur mémorisée initiale de la première valeur
22 newtree <- function (firstval, inc) {
23 m <- matrice (rep (NA, inc * 3), nrow = inc, ncol = 3)
24 m [1,3] <- firstval
25 retour (liste (mat = m, nxt = 2, inc = inc))
26}
27
28 # insère newval dans le sous-arbre de tr, avec la racine du sous-arbre étant
29 # à l'index hdidx; Notez que la valeur de retour doit être réaffectée à tr par le
30 # appelant (y compris ins () lui-même, en raison de la récurrence)
31 ins <- function (hdidx, tr, newval) {
Dans quelle direction ce nouveau noeud va-t-il, à gauche ou à droite?
33 dir <- if (newval <= tr $ mat [hdidx, 3]) 1 autre chose 2
34 # si lien nul dans cette direction, placez le nouveau noeud ici, sinon
35 # recurse
36 si (is.na (tr $ mat [hdidx, dir])) {
37 newidx <- tr $ nxt # où le nouveau nœud va
38 # Vérifiez la place pour ajouter un nouvel élément
39 si (tr $ nxt == nrow (tr $ mat) + 1) {

40 tr $ mat <-
41 rbind (tr $ mat, matrix (rep (NA, tr $ inc * 3), nrow = tr $ inc, ncol = 3))
42}
43 # insérer un nouveau noeud d'arbre
44 tr $ mat [newidx, 3] <- newval
45 # lien vers le nouveau noeud
46 tr $ mat [hdidx, dir] <- newidx
47 tr $ nxt <- tr $ nxt + 1 # prêt pour l'insertion suivante
48 retour (tr)
49} else tr <- ins (tr $ mat [hdidx, dir], tr, newval)
50}
Il existe une récurrence dans printtree () et ins (). Le premier est définitivement
Le plus facile des deux, alors regardons cela d'abord. Il imprime l'arbre, en trié
commande.
Rappelons notre description d'une fonction récursive f () qui résout un problème
De catégorie X: Nous avons f () divisé le problème X original en un ou plusieurs
Des problèmes X plus petits, appeler f () sur eux et combiner les résultats. Dans ce cas,
La catégorie X de notre problème consiste à imprimer un arbre, qui pourrait être un sous-arbre d'un
Plus grand. Le rôle de la fonction sur la ligne 13 est d'imprimer l'arbre donné,
Ce qu'il fait en s'identifiant aux lignes 15 et 18. Là, il imprime d'abord le côté gauche
Sous-arbre, puis la sous-arborescence droite, s'arrêtant pour imprimer la racine.
Cette pensée: imprime la sous-arborescence gauche, puis la racine, puis la droite
Sous-arbre, forme l'intuition en écrivant le code, mais encore une fois, nous devons faire
Assurez-vous d'avoir un mécanisme de terminaison approprié. Ce mécanisme est vu dans
Les énoncés if () dans les lignes 15 et 18. Lorsque nous arrivons à un lien nul, nous faisons
Ne continuez pas à vous guider.
La récurrence dans ins () suit les mêmes principes mais est considérablement
Plus délicat. Ici, notre "catégorie X" est une insertion d'une valeur dans une sous-arborescence.
Nous commençons à la racine d'un arbre, déterminons si notre nouvelle valeur doit
Entrez dans la sous-arborescence gauche ou droite (ligne 33), puis appelez à nouveau la fonction
Sur ce sous-arbre. Encore une fois, ce n'est pas dur en principe, mais un certain nombre de détails
Doit être pris en compte, y compris l'expansion de la matrice si nous avons fini de
Pièce (lignes 40-41).
Une différence entre le code récursif dans printtree () et ins () est
Que le premier comprend deux appels à lui-même, alors que celui-ci n'en a qu'un. Ce
Implique qu'il peut ne pas être difficile d'écrire ce dernier sous une forme non récursive.