Parmi les fonctions mathématiques les plus célèbres dans le domaine de l'informatique théorique et de la récursivité, la fonction d'Ackermann occupe une place tout à fait particulière. Introduite en 1926 par le mathématicien allemand Wilhelm Ackermann, cette fonction est devenue un exemple classique utilisé pour démontrer la puissance et les limites des algorithmes récursifs. Ce qui rend cette fonction particulièrement fascinante est sa croissance extrêmement rapide. Alors qu'une fonction exponentielle augmente déjà à un rythme impressionnant lorsque ses paramètres deviennent grands, la fonction d'Ackermann croît beaucoup plus vite encore. Pour certaines valeurs relativement modestes de ses paramètres, le résultat peut atteindre des nombres gigantesques dépassant rapidement les capacités de calcul ou de stockage des ordinateurs ordinaires. C'est précisément cette propriété ayant fait de la fonction d'Ackermann un sujet d'étude incontournable dans les cours de mathématiques discrètes, d'algorithmique et de théorie de la calculabilité.
La fonction est fréquemment citée dans les ouvrages consacrés à la récursivité, car elle constitue un exemple remarquable de fonction définie presque exclusivement à l'aide d'appels récursifs. Contrairement à de nombreuses fonctions mathématiques classiques, elle ne repose pas sur des boucles ou sur une formule algébrique directe. Chaque calcul entraîne généralement plusieurs nouveaux appels à la fonction elle-même, lesquels peuvent à leur tour générer d'autres appels récursifs. Cette structure provoque une explosion rapide du nombre d'opérations nécessaires lorsque les paramètres augmentent. Pour cette raison, la fonction d'Ackermann est souvent utilisée comme test de performance pour les implémentations récursives et comme exemple pédagogique permettant de comprendre les mécanismes d'empilement des appels de fonctions dans un programme.
Le programme en langage C présenté ci-dessous illustre une implémentation fidèle de cette célèbre fonction mathématique. La définition repose sur trois cas fondamentaux : lorsque le premier paramètre est nul, lorsque le second paramètre est nul, et enfin le cas général dans lequel la fonction s'appelle elle-même de manière imbriquée. Malgré la simplicité apparente du code, les calculs deviennent rapidement très exigeants lorsque les paramètres augmentent. Afin de conserver des temps d'exécution raisonnables, l'exemple se limite volontairement à de petites valeurs des paramètres M et N. Les résultats obtenus permettent néanmoins d'observer la progression caractéristique de la fonction et de constater à quel point sa croissance s'accélère rapidement. Cet exemple constitue une excellente démonstration de la récursivité pure en langage C et demeure l'un des classiques incontournables de la littérature mathématique et informatique consacrée aux fonctions récursives.
Voici un code source C effectuant le calcul de la fonction d'«Ackermann» dans ses positions inférieures :
- #include <stdio.h>
- #include <stdlib.h>
-
- int Ackermann(int M,int N) {
- if(M == 0) return N+1;
- else {
- if(N == 0) return Ackermann(M-1,1);
- else return Ackermann(M-1,(Ackermann(M,N-1)));
- }
- }
-
- int main()
- {
- int I,J;
- for(I=1;I<=2;I++) for(J=1;J<=10;J++) {
- printf("Ackermann(%i,%i)=%i\n",I,J,Ackermann(I,J));
- }
- return 0;
- }
on obtiendra le résultat suivant :
Ackermann( 1, 1)= 3Ackermann( 1, 2)= 4
Ackermann( 1, 3)= 5
Ackermann( 1, 4)= 6
Ackermann( 1, 5)= 7
Ackermann( 1, 6)= 8
Ackermann( 1, 7)= 9
Ackermann( 1, 8)= 10
Ackermann( 1, 9)= 11
Ackermann( 1, 10)= 12
Ackermann( 2, 1)= 5
Ackermann( 2, 2)= 7
Ackermann( 2, 3)= 9
Ackermann( 2, 4)= 11
Ackermann( 2, 5)= 13
Ackermann( 2, 6)= 15
Ackermann( 2, 7)= 17
Ackermann( 2, 8)= 19
Ackermann( 2, 9)= 21
Ackermann( 2, 10)= 23