La célèbre fonction d'Ackermann, proposée en 1926 par le mathématicien allemand Wilhelm Ackermann, est devenue au fil du temps l'un des exemples les plus connus lorsqu'il est question de récursivité en mathématiques et en informatique théorique. Cette fonction possède une propriété fascinante : sa croissance est extraordinairement rapide. Alors que les fonctions linéaires, quadratiques, polynomiales et même exponentielles augmentent déjà à des rythmes impressionnants, la fonction d'Ackermann dépasse largement ces catégories dès que les valeurs de ses paramètres deviennent un peu plus élevées. C'est précisément cette caractéristique qui lui a valu une place de choix dans les manuels consacrés aux algorithmes, à la théorie de la calculabilité et aux techniques de programmation récursive. Paradoxalement, bien que sa formule soit abondamment citée dans les ouvrages spécialisés et les cours universitaires, le nom de son créateur demeure relativement méconnu du grand public. La fonction d'Ackermann est également intéressante parce qu'elle constitue l'un des premiers exemples célèbres de fonction calculable qui n'est pas récursive primitive, démontrant ainsi les limites de certaines classes de fonctions mathématiques. Pour les programmeurs, elle représente un excellent exercice permettant de comprendre le fonctionnement des appels récursifs imbriqués et les conséquences qu'ils peuvent avoir sur la mémoire et les performances d'un programme. Le code source QuickBASIC/QBasic présenté ci-dessous illustre une implémentation directe et fidèle de cette fonction. Bien que l'exemple se limite volontairement à de petites valeurs des paramètres, afin d'éviter une explosion du nombre d'appels récursifs, il permet déjà d'observer la progression remarquable des résultats obtenus. En exécutant ce programme, vous pourrez constater comment une définition mathématique relativement courte est capable de générer des valeurs de plus en plus importantes, faisant de la fonction d'Ackermann un classique incontournable de l'informatique théorique, de la programmation récursive et de l'étude des fonctions à croissance extrêmement rapide.

Voici un code source QuickBASIC effectuant le calcul de la fonction d'«Ackermann» dans ses positions inférieures :

on obtiendra le résultat suivant :

Voir également

Science - Mathématique