Optimiser les fonctions récursives en les dérécursivant Par Godrik (godrik-article@mandragor.org) 

Optimiser les fonctions récursives en les dérécursivant.Par Godrik (godrik-article@mandragor.org) Definition
Récurrence: caractère de ce qui est récurrent, répétition d'un phénomène.
Récurrent: qui réapparaît, se reproduit.
Récursivité: propriété de ce qui est récursif.
Récursif: qui peut être répété de façon indéfinie.
Tel sont les définitions du Larousse. En informatique une chose sera récursive, quand elle est contenue dans elle même. (Vous savez, comme les Julia) Suivant cette définition, beaucoup de structure de données en informatique sont récursives. 

Un tableau: Zéro ou une case et un tableau.
Une liste: Zéro ou un élément, et un élément.
Un arbre binaire: rien ou un élément et deux arbres.
Un arbre n-aire: rien ou un élément et n arbres.
Des exemples d'algorithmes récursifs
Les algorithmes, suivant la même définition peuvent être récursif. Par exemple, le calcul du factoriel de n s'écrit: 

int factoriel (int n)
{
	if (n ==0 || n == 1)
		return 1;
	return n* factoriel(n-1);
}
Par exemple, un algorithme de somme d'un tableau d'entier peut utiliser la structure récursive du tableau. En C, nous aurons: 

int sommeTableau (int* tab, int size)
{
	if (size == 0)
		return 0;
	return tab[0] + sommeTableau(tab+1, size-1);
}
Lorsque nous avons écrit la fonction factoriel, nous avons utilisé la structure récursive des entiers naturels. 

Multi-récursion
Nous n'avons parlé jusqu'ici que de fonction mono-récursive (ou encore récursive de premier degré), mais il existe des algorithmes bi-récursif, ou n-recursif (ou encore récursif d'ordre n). Par exemple, le calcul de la profondeur d'un arbre binaire présente une double récursion. 

int profondeur (Arbre* a)
{
	if (!existe(a)) return 0;
	if (feuille(a)) return 1;
	return MAX(profondeur(a->filsGauche) + 1, profondeur(a->filsDroit) + 1);
}
Ou encore le calcul d'une suite de fibonacci en utilisant la structure multi-récursive des entiers. 

int fibonacci (int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}Récursivité terminale
Un algorithme récursif présente une récursivité terminale si et seulement si la valeur retourné par cet algorithme est une valeur fixe, ou une valeur calculée par cet algorithme. Selon cette définition, aucun des algorithmes si dessus ne présente de récursivité terminale. Pourquoi est ce que cette forme d'algorithme est intéressante pouvons nous nous demander ? Tout simplement parce qu’un algorithme en récursivité terminale est directement équivalent a une boucle de type "tant que" (boucle while). Les appels de fonctions étant des opérations complexe, avoir un algorithme en récursivité terminale (et donc une boucle tant que) est nettement plus rapide que sa version récursive "normal" (la complexité des deux versions reste bien évidement les mêmes) 

Alors, pourquoi est ce que factoriel, n'est pas sous forme récursive terminale ? Parce que tel que cette fonction est écrite, elle est équivalente à: 

int factoriel (int n)
{
	if (n ==0 || n == 1)
		return 1;
	int factnmoins1 = factoriel(n-1);
	int factn = n * factnmoins1;
	return factn;
}
On voit bien dans cette écriture que l'appel récursif à factoriel n'est pas la valeur renvoyé. 

Dérécursiver
Dérécursivé un algorithme récursif, c'est le mettre sous la forme d'une récursivité terminale. La première question est: "est ce que tout les algorithmes récursif sont dérécursivable ?" La réponse a cette question est NON. Le cas des multi-récursion est spéciale (voir le chapitre suivant). Et tout les algorithmes mono-récursif ne le sont pas non plus. Un algorithme est dérécursivable si la fonction enveloppante est associative et admet un élément neutre. 

Léger rappel d'algèbre: Une fonction f est associative, si et seulement si: pour tout x, y: f(x, y) = f(y, x). les opérateurs: + et * sont associatifs. - et / ne le sont pas (sauf si on exprime une soustraction comme une addition évidement) les fonctions MAX et MIN sont également associatives. 

Une fonction admet un élément neutre si et seulement si il existe E tel que pour tout x: f(x, E) = x L'opérateur + admet un élément neutre: 0 L'opérateur * admet 1 comme élément neutre. 

Fort de cette algèbre, qu'allons nous bien pouvoir dire de notre fonction factoriel ? Elle utilise une mono-récursion (return n * factoriel(n-1)). Cette récursion est englobé par l'opérateur * qui est associatif et dispose d'un élément neutre (1). Cette algorithme est donc dérécursivable. Pour qu'elle soit en récursivité terminale, il faut que la fonction n'aie pas besoin des appels précédants pour fournir le résultat. Il faut donc en quelque sorte que factoriel dispose de "l'historique" des appels précédents. Un paramètre de cumul des appels précédents s'impose alors et l'on écrit notre fonction: 

int factoriel (int n, int cumul)
{
	if (n == 1 || n == 0)
		return cumul;
	return factoriel (n-1, cumul*n);
}
Pour calculer factoriel de x nous écrirons donc "factoriel (x, 1);" 

Qu'avons nous fait précisément ? Nous utilisons l'élément neutre de la fonction multiplier comme valeur initiale de notre cumul. Le test d'arrêt de notre récursion reste toujours le même, mais renvoie maintenant le "panier" dans lequel nous avons accumulé nos valeurs. L'appel récursif remplit un peu plus le panier à chaque appel. 

Et avec de la multi-récursivité ?
Lorsque nous avons à faire a une multi-récursion, il est impossible de dérécursiver complètement. On peut néanmoins, dérécursiver partiellement nos opérations. En imbriquant les appels à la fonction récursive dans le but que l'un soit le paramètre de l'autre. Sur l'exemple de la suite de fibonacci, nous obtenons: 

int fibonacci(int n, int cumul)
{
	if (n == 0) return cumul;
	if (n == 1) return cumul+1;
	return fibonacci(n-1, fibonacci (n-2, cumul));
}ConclusionsJ'espère avoir répondu aux questions que vous vous posiez sur l'optimisation des fonctions récursives. La dérécursivité ne réduit pas la complexité des algorithmes en terme d'ordre, mais elle permet de réduire sensiblement les temps de calculs qui incombent aux appels de fonctions. Comme d'habitude, si des questions se posent après la lecture de mon article, vous avez mon adresse mail, ou pouvez me laisser un commentaire. 
Mandragor.org - 2004