Sobre a sua solução, você não está resgatando o valor da função em uma variável. Parece que tem uma ideia implícita em seu código que o valor da variável resultado
está sendo alterada na pilha de recursão, mas isso não ocorre.
Toda variável em C é passada por valor, não por referência (mais sobre o assunto). O que se chama de passagem por referência em C é a passagem do ponteiro da variável para dentro da função. O endereço em que a memória está armazenada fica então passível de modificação. Mas, se você analisar como o ponteiro é passado, ele em si é passado por valor, fazendo uma cópia do valor do ponteiro para dentro da função.
A primeira coisa que resolvi ver é o quão rápido crescia a função hiperfatorial. Encontrei então esse artigo no MathWorld, que me levou a essa sequência do OEIS. Vou botar aqui os valores n
, H(n)
e log2(H(n))
:
+---+---------------------+------------+
| n | H(n) | log2(H(n)) |
+---+---------------------+------------+
| 0 | 1 | 0 |
| 1 | 1 | 0 |
| 2 | 4 | 2 |
| 3 | 108 | 6.75 |
| 4 | 27648 | 14.8 |
| 5 | 86400000 | 26.4 |
| 6 | 4031078400000 | 41.9 |
| 7 | 3319766398771200000 | 61.5 |
+---+---------------------+------------+
Isso significa que, com o argumento de entrada 6
, estouramos a capacidade de armazenamento de um long int
(32 bits)!! Com 7
chegamos ao limite da capacidade de armazenamento de 64 bits. Não cheguei a ver o valor para H(8)
, mas com certeza vai estourar e muito a capacidade do long long int
.
Note que a quantidade de bits necessárias para armazenar a informação de um número n
qualquer é floor(log2(x)) + 1
. Então podemos transformar a tabela acima para acomodar a quantidade de bits:
+---+------------+---------+
| n | log2(H(n)) | bits(n) |
+---+------------+---------+
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 2 | 2 | 3 |
| 3 | 6.75 | 7 |
| 4 | 14.8 | 15 |
| 5 | 26.4 | 27 |
| 6 | 41.9 | 42 |
| 7 | 61.5 | 62 |
+---+------------+---------+
Assumindo que a questão não queira que você implemente um número inteiro com capacidade arbitrária, então vamos a uma solução que respeita os limites da representação do número inteiro usando apenas aritmética inteira.
A função hiperfatorial
é uma função pura, portanto sujeita a memoização. Vou definir um código de erro -1
quando se tenta usar um número conhecido a dar overflow numérico.
Além disso, internamente vou precisar usar uma função de potenciação inteira. Vou começar por ela.
De modo ingênuo, a função de potenciação inteira poderia ser feita assim:
long long int int_pow_ingenuo(int base, int expoente) {
long long int resultado = 1;
int i;
for (i = 0; i < expoente; i++) {
resultado *= base;
}
return resultado;
}
Essa alternativa é ingênua porque faz sempre O(expoente)
operações de multiplicação. Podemos melhorar essa alternativa para executar em o(lg(expoente))
operações de multiplicação.
A alternativa para isso é:
- dividir em dois o expoente
- calcular essa exponenciação com essa metade do expoente
- multiplicar o resultado anterior por ele mesmo
- caso o expoente seja ímpar, multiplicar o resultado anterior pela base
Vou levar como base da recursão os valores:
0
: retorna sempre 1
1
: retorna o valor base
2
: retorna o valor base multiplicado por ele mesmo
Ficaria assim esse exponenciação:
long long int int_pow(int base, int expoente) {
long long int resultado_parcial;
switch (expoente) {
case 0:
return 1;
case 1:
return base;
case 2:
return base * base;
}
resulta_parcial = int_pow(base, expoente/2);
if (expoente % 2 == 1) {
return resulta_parcial * resulta_parcial * base;
} else {
return resulta_parcial * resulta_parcial;
}
}
Note que int_pow
também é uma função pura, mas como ela só é usada internamente, não me é interessante.
Agora, o código para hiperfatorial
. O primeiro passo são os casos básicos:
Os demais casos serão feitos através da memoização. Vou chamar o vetor de memoização dessa função de memo_hiperfatorial
. Como só se interessa os valores no intervalo [0, 7]
e o caso base é hiperfatorial(0) = 1
, vamos iniciar o vetor com valores zero para todos os casos, exceto memo_hiperfatorial[0]
, que vale 1
. A inicialização que escolhi é assim:
static long long int memo_hiperfatorial[8] = { 1, 0, 0, 0, 0, 0, 0, 0 };
Botei a variável como estática para isolá-la. Pensei inicialmente em por ela na unidade de compilação, mas sendo estática ela pode tranquilamente ficar na função.
Avançando um pouco mais na escrita da função, podemos assumir que valores previamente memoizados já podem ser retornados imediatamente. Um valor é identificado como memoizado caso memo_hiperfatorial[n] != 0
(para o contexto desta resposta, existem outras alternativas com outras estratégias).
long long int hiperfatorial(int n) {
static long long int memo_hiperfatorial[8] = { 1, 0, 0, 0, 0, 0, 0, 0 };
if (n >= 8 || n < 0) {
return -1;
}
if (memo_hiperfatorial[n] != 0) {
return memo_hiperfatorial[n];
}
...
}
Pronto, agora só falta o passo que se favorece da recursão para alcançar o próximo valor. Pela definição, hiperfatorial pode ser escita assim:
Então o passo recursivo seria:
return int_pow(n, n) * hiperfatorial(n - 1);
Para atualizar os valores memoizados:
return memo_hiperfatorial[n] = int_pow(n, n) * hiperfatorial(n - 1);
Portanto, juntando tudo (e recapitulando int_pow
):
long long int int_pow(int base, int expoente) {
long long int resultado_parcial;
switch (expoente) {
case 0:
return 1;
case 1:
return base;
case 2:
return base * base;
}
resulta_parcial = int_pow(base, expoente/2);
if (expoente % 2 == 1) {
return resulta_parcial * resulta_parcial * base;
} else {
return resulta_parcial * resulta_parcial;
}
}
long long int hiperfatorial(int n) {
static long long int memo_hiperfatorial[8] = { 1, 0, 0, 0, 0, 0, 0, 0 };
if (n >= 8 || n < 0) {
return -1;
}
if (memo_hiperfatorial[n] != 0) {
return memo_hiperfatorial[n];
}
return memo_hiperfatorial[n] = int_pow(n, n) * hiperfatorial(n - 1);
}
H(n) = 1² * 2² * 3² * 4² * ... * n²
?