Chapitre 2 Récursivité

Chapitre 2 Récursivité

Les définitions par récurrence sont assez courantes en mathématiques. Prenons le cas de la suite de Fibonacci, définie par

u₀ = u₁ = 1

u_n = u_n-1 + u_n-2 pour n > 1

On obtient donc la suite 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,...Nous allons voir que ces définitions s'implémentent très simplement en informatique par les définitions récursives.


2.1 Fonctions récursives


2.1.1 Fonctions numériques

Pour calculer la suite de Fibonacci, une transcription littérale de la formule est la suivante:

static int fib (int n) {

if (n <= 1)
return 1;
else
return fib (n-1) + fib (n-2);
}
fib est une fonction qui utilise son propre nom dans la définition d'elle-même. Ainsi, si l'argument n est plus petit que 1, on retourne comme valeur 1. Sinon, le résultat est fib(n-1) + fib(n-2). Il est donc possible en Java, comme en beaucoup d'autres langages (sauf Fortran), de définir de telles fonctions récursives. D'ailleurs, toute suite á u_n ñ définie par récurrence s'écrit de cette manière en Java, comme le confirment les exemples numériques suivants: factorielle et le triangle de Pascal.

static int fact(int n) {

if (n <= 1)
return 1;
else
return n * fact (n-1);
}

static int C(int n, int p) {

if ((n == 0) || (p == n))
return 1;
else
return C(n-1, p-1) + C(n-1, p);
}
On peut se demander comment Java s'y prend pour faire le calcul des fonctions récursives. Nous allons essayer de le suivre sur le calcul de fib(4). Rappelons nous que les arguments sont transmis par valeur dans le cas présent, et donc qu'un appel de fonction consiste à évaluer l'argument, puis à se lancer dans l'exécution de la fonction avec la valeur de l'argument. Donc

fib(4) -> fib (3) + fib (2)
-> (fib (2) + fib (1)) + fib (2)
-> ((fib (1) + fib (1)) + fib (1)) + fib(2)
-> ((1 + fib(1)) + fib (1)) + fib(2)
-> ((1 + 1) + fib (1)) + fib(2)
-> (2 + fib(1)) + fib(2)
-> (2 + 1) + fib(2)
-> 3 + fib(2)
-> 3 + (fib (1) + fib (1))
-> 3 + (1 + fib(1))
-> 3 + (1 + 1)
-> 3 + 2
-> 5

<BLOCKQUOTE></BLOCKQUOTE>Il y a donc un bon nombre d'appels successifs à la fonction fib (9 pour fib(4)). Comptons le nombre d'appels récursifs R_n pour cette fonction. Clairement R₀ = R₁ = 1, et R_n = 1 + R_n-1 + R_n-2 pour n > 1. En posant R'_n = R_n + 1, on en déduit que R'_n = R'_n-1+ R'_n-2 pour n > 1, R'₁ = R'₀ = 2. D'où R'_n = 2 × fib(n), et donc le nombre d'appels récursifs R_n vaut 2 × fib(n) - 1, c'est à dire 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,... Le nombre d'appels récursifs est donc très élevé, d'autant plus qu'il existe une méthode itérative simple en calculant simultanément fib(n) et fib(n-1). En effet, on a un calcul linéaire simple


Ce qui donne le programme itératif suivant

static int fib(int n) {

int u, v;
int u0, v0;
int i;

u = 1; v = 1;
for (i = 2; i <= n; ++i) {
u0 = u; v0 = v;
u = u0 + v0;
v = v0;
}
return u;
}
Pour résumer, une bonne règle est de ne pas trop essayer de suivre dans les moindres détails les appels récursifs pour comprendre le sens d'une fonction récursive. Il vaut mieux en général comprendre synthétiquement la fonction. La fonction de Fibonacci est un cas particulier car son calcul récursif est particulièrement long. Mais ce n'est pas le cas en général. Non seulement, l'écriture récursive peut se révéler efficace, mais elle est toujours plus naturelle et donc plus esthétique. Elle ne fait que suivre les définitions mathématiques par récurrence. C'est une méthode de programmation très puissante.

2.1.2 La fonction d'Ackermann

La suite de Fibonacci avait une croissance exponentielle. Il existe des fonctions récursives qui croissent encore plus rapidement. Le prototype est la fonction d'Ackermann. Au lieu de définir cette fonction mathématiquement, il est aussi simple d'en donner la définition récursive en Java

static int ack(int m, int n) {

if (m == 0)
return n + 1;
else
if (n == 0)
return ack (m - 1, 1);
else
return ack (m - 1, ack (m, n - 1));
}
On peut vérifier que


Donc ack(5, 1) » ack(4, 4) » 2⁶⁵⁵³⁶ > 10⁸⁰, c'est à dire le nombre d'atomes de l'univers.

2.1.3 Récursion imbriquée

La fonction d'Ackermann contient deux appels récursifs imbriqués, c'est ce qui la fait croître si rapidement. Un autre exemple est la fonction 91 de MacCarthy

static int f(int n) {

if (n > 100)
return n - 10;
else
return f(f(n+11));
}
Ainsi, le calcul de f(96) donne f(96) = f(f(107)) = f(97) = ··· f(100) = f(f(111)) = f(101) = 91. On peut montrer que cette fonction vaut 91 si n £ 100 et n - 10 si n > 100. Cette fonction anecdotique, qui utilise la récursivité imbriquée, est intéressante car il n'est pas du tout évident qu'une telle définition donne toujours un résultat.¹ Par exemple, la fonction de Morris suivante

static int g(int m, int n) {

if (m == 0)
return 1;
else
return g(m - 1, g(m, n));
}
Que vaut alors g(1, 0)? En effet, on a g(1, 0) = g(0, g(1, 0)). Il faut se souvenir que Java passe les arguments des fonctions par valeur. On calcule donc toujours la valeur de l'argument avant de trouver le résultat d'une fonction. Dans le cas présent, le calcul de g(1,0) doit recalculer g(1, 0). Et le calcul ne termine pas.