Aller-retour sur un intervalle

• Si $[i:j]$ est vide ($i=j$), il n'y a rien à afficher. Sinon, l'aller-retour de $[i:j]$ est : $i$, puis l'aller-retour de $[i+1:j]$, puis de nouveau $i$.

static void allerRetour(int i, int j) {
    if (i == j) return;               // [i:i] vide : affiché sans rien faire
    System.out.print(i + " ");        // (1) i, en tête de l'aller
    allerRetour(i + 1, j);            // (2) aller-retour de [i+1:j] affiché
    System.out.print(i + " ");        // (3) i, en fin de retour
}                                     // (1)(2)(3) : aller-retour de [i:j] affiché

allerRetour(0,4) : 0 1 2 3 3 2 1 0

L'affichage avant l'appel récursif donne l'ordre croissant, celui qui suit l'appel donne l'ordre décroissant : les affichages « en remontant » se font dans l'ordre inverse des appels. -

static void arcMoities(int i, int j) {
    if (j - i <= 0) return;           // intervalle vide
    int k = (i + j) / 2;              // i <= k < j
    arcMoities(i, k);                 // [i:k] affiché croissant
    System.out.print(k + " ");        // puis k
    arcMoities(k + 1, j);             // puis [k+1:j] : [i:j] affiché croissant
}

arcMoities(0,10) : 0 1 2 3 4 5 6 7 8 9  (profondeur max 4)

La fonction arc du cours retire une valeur par appel : sa profondeur est $n=j-i$. Ici la taille est divisée par deux à chaque niveau : la profondeur est de l'ordre de ${\log }_{2}n$ (ici $4$ pour $n=10$). Les deux fonctions affichent les $n$ valeurs en $\Theta (n)$, mais seule la seconde supporte $n=10^6$ sans dépassement de la pile d'appels.