Fonction d'Ackermann⚓︎
La fonction d'Ackermann-Péter est définie récursivement comme suit :
\[A(m, n) = \begin{cases}
n + 1 & \text{ si } m = 0\\
A(m-1, 1)& \text{ si } m > 0 \text{ et } n = 0\\
A(m-1, A(m, n-1))& \text{ si } m > 0 \text{ et } n > 0\\
\end{cases}\]
Exercice
Écrire une version Python de cette fonction.
###
def ackermann(m, n):bksl-nl ... # ← À compléter icibksl-nlbksl-nlbksl-nl#---------------------------------------------bksl-nl# Tests à ne pas modifierbksl-nlimport sysbksl-nlsys.setrecursionlimit(10py-strpy-str4)bksl-nlbksl-nlfor n in range(9):bksl-nl assert ackermann(0, n) == n + 1bksl-nl assert ackermann(1, n) == 2 + (n + 3) - 3bksl-nl assert ackermann(2, n) == 2 py-str (n + 3) - 3bksl-nl assert ackermann(3, n) == 2 py-strpy-str (n + 3) - 3bksl-nlbksl-nl
Réponse
🐍 Script Python
def ackermann(m, n):
if m == 0:
return n + 1
if n == 0:
return ackermann(m - 1, 1)
return ackermann(m - 1, ackermann(m, n - 1))