La récursivité naïve — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 1)

La récursivité naïve

Glouton ou dynamique ? · niveau 2

Énoncé

On programme la récurrence de Zébulon « directement » :


static int m(int[] R, int j) {
    if (j == 0) return R[0];
    if (j == 1) return MOINS_INFINI;
    if (j == 2) return R[0] + R[2];
    return Math.max(m(R, j-2), m(R, j-3)) + R[j];
}

Montrer que le nombre d'appels $a (j)$ provoqués par l'appel m(R, j) vérifie $a (j) = 1 + a (j - 2) + a (j - 3)$ .
Calculer $a (j)$ pour $j = 20, 40, 60, 80$ . Conclure.
(Mémoïsation) Modifier la fonction pour qu'elle mémorise dans un tableau les valeurs déjà calculées. Combien d'appels fait-elle alors pour $j = 80$ ? Quelle est sa complexité ?

Corrigé

Pour $j \leq 2$ , l'appel ne provoque aucun autre appel : $a (0) = a (1) = a (2) = 1$ . Pour $j \geq 3$ , l'appel m(R, j) compte pour un, puis provoque l'appel m(R, j-2) (qui en provoque $a (j - 2)$ au total) et l'appel m(R, j-3) ( $a (j - 3)$ au total) : $a (j) = 1 + a (j - 2) + a (j - 3)$ .
On calcule $a (j)$ par la récurrence elle-même (et on vérifie par un compteur placé dans la fonction) :


a(20) = 399
a(40) = 110809
a(60) = 30693571
a(80) = 8501898223

Le nombre d'appels est multiplié par environ $280$ chaque fois que $j$ augmente de $20$ : croissance exponentielle (en $1, 3 2^{j}$ , comme le nombre de chemins). Pour $j = 80$ , plus de huit milliards d'appels pour calculer 81 valeurs. La fonction recalcule sans cesse les mêmes $m (i)$ .

On ajoute un tableau Integer[] memo, initialement rempli de null :


static int mMemo(int[] R, int j, Integer[] memo) {
    if (memo[j] != null) return memo[j];           // déjà calculée
    int v;
    if (j == 0) v = R[0];
    else if (j == 1) v = MOINS_INFINI;
    else if (j == 2) v = R[0] + R[2];
    else v = Math.max(mMemo(R, j-2, memo), mMemo(R, j-3, memo)) + R[j];
    memo[j] = v;                                    // mémorisée une fois pour toutes
    return v;
}

Pour $j = 80$ , le compteur affiche $155$ appels. Chaque valeur $m (i)$ n'est calculée qu'une fois, et chaque calcul provoque au plus deux appels : la complexité est $Θ (j)$ , comme celle de calculerM. La mémoïsation est la version « descendante » de la programmation dynamique ; le tableau rempli par $j$ croissants en est la version « ascendante ».