Les algorithmes récursifs

Accueil‎ > ‎

Un algorithme est dit récursif lorsqu’il intervient dans sa propre description, c'est a dire lorsque il est défini en fonction de lui même.

Toutes fonction calculable est représentée par une machine de Turing; les machines de turing sont équivalentes aux fonctions récursives. La thèse de Church est formulée en disant que des règles formelles de calcul (machines de Turing, les fonctions λ-définissables, les fonctions récursives..) formalisent correctement la notion de méthode effective de calcul.

On considère généralement qu'une méthode effective de calcul doit satisfaire aux obligations suivantes :

l'algorithme consiste en un ensemble fini d'instructions simples et précises qui sont décrites avec un nombre limité de symboles ;
l'algorithme doit toujours produire le résultat en un nombre fini d'étapes ;
l'algorithme peut en principe être suivi par un humain avec seulement du papier et un crayon ;
l'exécution de l'algorithme ne requiert pas d'intelligence de l'humain sauf celle qui est nécessaire pour comprendre et exécuter les instructions.

Un exemple d'une telle méthode est l'algorithme d'Euclide pour déterminer le plus grand commun diviseur d'entiers naturels ou celui qui détermine pour un entier n la longueur de la suite de Goodstein qui commence en n.

Il s'agit là d'une définition intuitive assez claire, mais pas d'une définition formelle, faute d'avoir précisé ce qu'on entend par « instruction simple et précise » ou par « l'intelligence requise pour exécuter les instructions ». On peut en revanche définir formellement ce qu'est un algorithme et pour cela on a le choix entre divers formalismes. À ce stade, la thèse de Church affirme que les deux notions, intuitive de « méthode effective », et formelle (« règles de calcul », ou « algorithme »), concordent, apportant ainsi une définition rigoureuse du concept de calculabilité.

Donc si pour un problème donné un algorithme existe l'algorithme récursif existe aussi, et vice versa. Dans beaucoup de situation l'algorithme récursif est plus simple à trouver. Vous devez absolument maitriser cette technique de programmation. Nous verrons plus tard comment traduire les algorithmes récursif en algorithme itératif (avec boucle).

Dans cette section "Algorithmes récursifs" nous décrirons quelques exemple d'algorithmes naturellement récursifs.

Exemples introductifs

Soit la fonction puissance: puis(x:R,n:N)->(xn:R)

On a puiss(x,0)=1; et pour (n>0) puiss(x,n)=x*puiss(x,n-1);

d'ou la méthode Java

public static puiss(double x, int n) {
    if (n==0) return 1;
    else return (x*puiss(x,n-1));
}

Etude de performances

Ici pour n donné la fonction puiss sera appelée n fois, or nous pouvons constaté que si n est pair: puiss(x,n)=puiss(x,n/2)*puiss(x,n/2) et si n est impair: puiss(x,n)=x*puiss(x,(n-1)/2)*puiss(x,(n-1)/2 d'où la méthode Java suivante:

public static puiss(double x, int n) {
    if (n==0) return 1;
    // si on est ici c'est que n!=0
    int par=puiss(x,n/2); // en java l'opérateur / est la division entière
    if ((n%2)==0) return par*par; // % est l'opérateur modulo
    else return x*par*par;
}

Combien d'appel à puiss y à-t-il cette fois?

Sous-pages (2) : Algorithme Euclide Le binome de newton C(n,p)

Comments