fonction d'Ackermann

ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Fonction récursive d'Ackermann » Autres cas récursifs dans ChronoMath
» Notion de fonction récursive , fonction de Sudan

Dans sa version de N² dans N, la fonction d'Ackermann est la fonction récursive définie par :

A(0,n) = n+1;
m ≥ 1, A(m,0) = A(m-1,1);
m ≥ 1, n ≥ 1, A(m,n) = A(m-1,A(m,n-1)).

Programmation JavaScript récursif de la fonction :

<SCRIPT LANGUAGE=JavaScript>
function acker()
{
m=3
m=eval(prompt("A(m,n), donnez m : ",m))
n=2
n=eval(prompt("A(m,n), donnez n : ",n))
alert("A("+m+" , "+n+") = "+A(m,n))
}

function A(m,n)
{
if (m!=0 && n!=0)
{return A(m-1,A(m,n-1))}
else
{
if (m==0) {return n+1}
if (n==0) {return A(m-1,1)}
}
}
</SCRIPT>

➔ Le programme ne contrôle pas les entrées qui devront être entières ! La structure récursive de la fonction A(m,n) présente une programmation identique à sa définition mathématique. C'est là l'élégance et la concision des définitions récursives comme celle, plus simple, du PGCD.

! le programme sature très vite !
C'est le problème général des programmes récursifs devant "empiler" en mémoire les résultats intermédiaires.
Un micro-ordinateur, quoique doté d'un compilateur JavaScript relativement puissant, n'est pas "vraiment" adapté à ce type de calcul doublement récursif.

!
A(4,1) est déjà problématique !!!

➔ Pour en savoir plus :

Techniques récursives en programmation par D.W. Baron, Éd. Dunod, Paris - 1970
Les bases de la programmation par Jacques Arsac, Éd. Dunod informatique, Paris - 1983
Les algorithmes par Patrice Hernert - Que sais-je n° 2928, Ed. P.U.F., Paris - 1995