Implementación de algoritmos de teoría de números/Función de Ackermann

La función de Ackermann es una función matemática recursiva encontrada en 1926 por Wilhelm Ackermann, tiene un crecimiento extremadamente rápido, de interés para la ciencia computacional teórica y la teoría de la computabilidad. Esta función toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue:

$A(m,n)={\begin{cases}n+1,&{\mbox{si }}m=0;\\A(m-1,1),&{\mbox{si }}m>0{\mbox{ y }}n=0;\\A(m-1,A(m,n-1)),&{\mbox{si }}m>0{\mbox{ y }}n>0\end{cases}}$

Implementación en distintos lenguajes de programación

Código en Java

public static 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)));
}

Código en C

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

Código en Lisp

(defun ackermann (m n)
  (cond ((= m 0) (1+ n))
        ((= n 0) (ackermann (1- m) 1))
        (t (ackermann (1- m)
                      (ackermann m (1- n))))))

Código en Haskell

ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))

Véase también: Haskell

Código en Prolog

ackermann(0,N,R):- R is N+1.
ackermann(M,0,R):- M1 is M-1,
                   ackermann(M1,1,R).
ackermann(M,N,R):- M1 is M-1,
	           N1 is N-1,
		   ackermann(M,R1,M1),
		   ackermann(M1,R1,R).

Código en Ada

function Ackermann (m, n : Integer) return Integer is
begin
    if m = 0 then
        return n + 1;
    elsif m > 0 and n = 0 then
        return Ackermann (m - 1, 1);
    elsif m > 0 and n > 0 then
        return Ackermann (m - 1, Ackermann (m, n - 1));
    end if;
end Ackermann;

Código en Pascal

program funcion_de_ackermann; {compatible hasta el par(4,0)}
uses crt;
procedure leerpar(var m, n : Integer);
begin
    writeln('Ingrese un numero: ');
    readln(m);
    writeln('Ingrese el otro numero: ');
    readln(n);
end;
function ackermann(m, n : Integer) : LongInt;
begin
    if m = 0 then
        ackermann := n + 1
    else if (m > 0) and (n = 0) then
        ackermann := ackermann(m - 1, 1)
    else if (m > 0) and (n > 0) then
        ackermann := ackermann(m - 1, ackermann(m, n - 1));
end;

var m, n : Integer;

begin
    clrscr;
    leerpar(m,n);
    writeln(ackermann(m, n));
    readkey;
end.

Código en Python

def ackermann(n, m):
    if n == 0:
        return m + 1
    elif m == 0:
        return ackermann(n - 1,1)
    else:
        return ackermann(n - 1, ackermann(n, m - 1))

Véase también: Python

Código en Ruby

def ackermann(m, n)
  return n + 1                                 if m == 0
  return ackermann(m - 1, 1)                   if m > 0 && n == 0
  return ackermann(m - 1, ackermann(m, n - 1)) if m > 0 && n > 0
end