La fonction d’ACKERMANN

La théorie de la récursivité ou Théorie de la calculabilité, est une notion appartenant à la fois à la logique mathématique et à l’informatique théorique. Cette notion, du moins sa formalisation, est née vers les années 1930, période riche en découvertes mathématiques ; elle permet notamment de trouver, algorithmiquement, une fonction calculable, et par conséquent de juger des limites de nos ordinateurs (computer = calculateur) sur certains algorithmes. Une fonction récursive étant une fonction qui peut s’exprimer en s’utilisant elle-même.

Exemple : la fonction factorielle : n!=n×(n-1)!
On utilise le terme factorielle « ! » des deux cotés de l’égalité).

La fonction d’ACKERMANN, à l’instar de la suite de Fibonacci qui croit de manière exponentielle, est une fonction récursive à très forte croissance (c’est là un excellent euphémisme), définie initialement en 1928 par le mathématicien Wilhelm Ackermann (29 mars 1896 à Herscheid - 24 décembre 1962 à Lüdenscheid), alors étudiant sous la direction du célèbre David HILBERT (23 janvier 1862 à Königsberg, Prusse-Orientale - 14 février 1943 à Göttingen, Allemagne), incontestablement l’un des plus grands mathématiciens du siècle dernier. Cette fonction fut initialement définie avec 3 valeurs en entrée :




C’est ensuite le mathématicien Ròzsa Péter qui donna à la fonction d’Ackermann sa forme que nous connaissons et utilisons actuellement : elle prend seulement 2 valeurs en entrée.



On montre de manière récurrente la définition suivante de la fonction :

A(m,n)= 2↑(m-2)(n + 3)- 3

On peut voir ici l’utilisation des puissances itérées de Knuth (« ↑ »).


Il est facile de coder cette fonction en C, c’est ce que je vous propose de faire à présent :

--------------------------------------------------------------------------------------------
#include stdio.h // N'oubliez pas les crochets que j'ai du enlever

main ()
{
/**
C’est dans le programme principal (main) que sera testée
notre fonction ackermann(…)
=========================================
*/

int ackermann (int, int) // Il faut bien sûr déclarer
// la fonction avant de l’utiliser.
Sa définition est faite plus bas.

int m,n;

printf ("Donnez m et n :\t");
scanf ("%d,%d", &m, &n) ;
printf("\n");
printf ("ackermann (%d,%d)= %d", m, n, ackermann(m,n) );
printf("\n");

/**
Dans cette partie, on définit la fonction, donc ce qu’elle devra faire
avec les paramètres mis en entrée
Attention : entrer des valeurs négative n’est pas correcte
*/

int ackermann (int m, int n)
{
if (m<0) style="font-weight: bold; color: rgb(0, 0, 153);">else if (m==0) return (n+1) ;
else if (n==0) return ( ackermann(m-1,1) ) ;
else return ackermann ( m-1, ackermann(m,n-1) ) ;
}
}

-------------------------------------------------------------------------------------------------
Exemple d’exécution :

Donnez m et n : 2,3
ackermann (2,3)= 9

Attention, la fonction d’Ackermann croît très vite, évitez donc d’utiliser de trop grandes valeurs . À titre d’exemple : A(4,2) contient 19729 chiffres, c’est quand même énorme !