Exercice : Fonction d’Ackermann

Exercice : Fonction d’Ackermann#

Attention, dans cet exercice, l’exécution de certains programmes peut être très longue, il est possible d’interrompre l’exécution à l’aide de la commande Controle-C dans un terminal.

On appelle fonction d’Ackermann la fonction définie de la manière suivante : $$A(m,n)=\begin{cases} n+1 &\text{ si $m=0$ } \\ A(m-1,1) &\text{ si $m>0$ et $n=0$ } \\ A(m-1,A(m,n-1)) &\text{ sinon } \end{cases} $$

Est-ce que cette fonction va bien toujours se terminer ?

BEGIN SOLUTION

À chaque appel récursif, seuls deux cas sont possibles, soit $m$ décroit et $n$ peut alors prendre n’importe quelle valeur, soit $m$ reste constant mais $n$ décroit.

On en déduit que $m$ va lentement tendre vers 0 à une vitesse qui va dépendre des valeurs que prendra $n$ à chaque étape.

La fonction va donc bien toujours se terminer (il n’y a pas de suite infinie décroissante pour les entiers naturels).

END SOLUTION

Implémentez la fonction d’Ackerman et testez la pour les couples $(2,2)$, $(2,3)$, $(3,3)$ et $(4,1)$. Que remarquez-vous ?

BEGIN SOLUTION

int ack(int m, int n) {
    if (m == 0)
        return n + 1;
    if (n == 0)
        return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}
int main() {
    int m, n;
    cin >> m >> n;
    cout << ack(m, n) << endl;
    return 0;
}

Pour le couple $(4,1)$ la valeur obtenue : $65533$ n’est pas très grande mais le temps d’exécution est énorme.

END SOLUTION

Modifiez votre code afin de compter le nombre d’appels de la fonction récursive et l’afficher avec le résultat du calcul. Que remarquez-vous ?

BEGIN SOLUTION
```
long c = 0;
int ack(int m, int n) {
    c++;
    if (m == 0)
        return n + 1;
    if (n == 0)
        return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}
int main() {
    int m, n;
    cin >> m >> n;
    cout << ack(m, n) << endl;
    cout << c << endl;
    return 0;
}
```
Les deux appels imbriqués engendrent un très grand nombre d’appels récursifs et donc un très long temps de calcul. Le couple $(4,1)$ demande près de 3 milliards d’appels pour terminer.

Le compteur du nombre d’appels est de type long et non int car le nombre d’appels est trop grand pour tenir dans un int. Si on le déclare int, on risque un dépassement de capacité.

END SOLUTION