Função Ackermann

Uma das mais importantes funções na ciência da computação. Sua maior propriedade é que ela cresce surpreendentemente rápido pois esta função eleva seu retorno rapidamente para números muito grandes, denominados números Ackermann e que normalmente são representados em uma notação inventada por Donald Knuth, a notação "up-arrow" ou notação de Knuth.

A função Ackermann foi descoberta e estudada por Wilhelm Ackermann em 1928. A função que ele descobriu, que então recebeu seu nome, é um simples exemplo de uma função total e bem definida que pode ser computável mas não é uma recursão primitiva. "Total e bem definida" significa que a função é internamente consistente e não quebra as regras das instruções que a define. "Computável" significa que ela pode, em princípio, ser avaliada por todos os valores possíveis em suas variáveis. "Recursão primitiva" significa que pode ser computada usando somente laços for, repetindo a operação em um número de vezes predeterminado. A função Ackermann somente pode ser calculada usando o laço de repetição while, que repete a ação até que o teste da condição retorne falso.

A função Ackermann é definida recursivamente para números inteiros não negativos, m e n, como:

          n + 1                  se m = 0
A(m, n) = A(m - 1, 1)            se m > 0 e n = 0
          A(m - 1, A(m, n - 1))  se m > 0 e n > 0

Dois inteiros positivos, m e n, são a entrada e A(m ,n) é a saída sendo outro inteiro positivo. A função pode ser programada facilmente em apenas poucas linhas de código. O problema não é a complexidade da função mas sua terrível taxa de crescimento. Por exemplo uma inocente entrada A(4,2) retorna um número de 19.729 dígitos:

A(0, n) = n + 1
A(1, n) = 2 + (n + 3) - 3
A(2, n) = 2 × (n + 3) - 3
A(3, n) = 2^(n + 3) - 3
A(4, n) = 2^(2^(...^2)) - 3 (n + 3 números dois)
A(5, n) = 2^(2^(...^2))^(2^(2^(...^2)))^(...^(2^(2^(...^2)))) - 3

Por isso o uso de uma grafia especial para números grandes como a notação de Knuth é indispensável, como mostra o exemplo abaixo:

A(4, n) = 2^^(n + 3) - 3
A(5, n) = 2^^^(n + 3) - 3

Como podem perceber, a função Ackermann estabelece adições iterativas e multiplicações iterativas, efetuando potências dentro de potências, recursivamente (potências iterativas). Alguns resultados da função Ackermann para as entradas m e n são mostrados abaixo:

                             n
          0      1           2             3    4    5
   0      1      2           3             4    5    6
m  1      2      3           4             5    6    7
   2      3      5           7             9   11   13
   3      5     13          29            61  125  253
   4     13  65533  2^65536 -3  2^2^65536 -3  ...
   5  65533  ...

O código para a função Ackermann é bastante simples, abaixo dois exemplos em java que aplicam a função:

public static long acker(long m, long n) {
  if(m == 0) {
        return n + 1;
  } else if(n == 0) {
        return acker(m-1, 1);
  } else {
        return acker(m-1, acker(m, n-1));
  }
}

Ou:

public static long acker(long m, long n) {
  return (m == 0) ? (n + 1) : ((n == 0) ? acker(m-1, 1) : acker(m-1, acker(m, n-1)));
}

A função Ackermann devido a sua característica de recursão extremamente profunda pode ser usada como teste de medida da capacidade de um compilador otimizar a recursão.

Veja mais em:

http://mathworld.wolfram.com/AckermannFunction.html
http://rosettacode.org/wiki/Ackermann_Function
http://planetmath.org/encyclopedia/AckermannFunction.html
http://kosara.net/thoughts/ackermann.html