Aller au contenu

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))