5

Estou tentando fazer um programa com uma função recursiva pra retornar um hiperfatorial de um número em C, porém, o único valor que a função retorna é 1. Onde estou errando?

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int hiperfatorial(int n,int i, int resultado) {

    if (i==n) 
        return;

    i++;
    resultado*=pow(i,i);

    return hiperfatorial(n,i,resultado);
}

int main() {

    int n,i=1,resultado=1;
    printf("\nDigite um numero: ");
    scanf("%i", &n);
    hiperfatorial (n,i,resultado);

printf("\nO hiperfatorial desse numero eh: %i", resultado);
    return 0;
}
10
  • Qual a definição de "hiperfatorial"? Commented 16/11/2017 às 18:35
  • Quanto deveria dar se entrasse 5 por exemplo?
    – Maniero
    Commented 16/11/2017 às 18:38
  • Por alguma razão não consigo fazer os símbolos de ao quadrado e ao cubo nesse teclado por isso que tive que fazer essa bagunça de parenteses.
    – Bruno Lobo
    Commented 16/11/2017 às 18:40
  • Seria H(n) = 1² * 2² * 3² * 4² * ... * n²?
    – Woss
    Commented 16/11/2017 às 18:42
  • Não Anderson, seria cada numero tendo como exponencial ele mesmo
    – Bruno Lobo
    Commented 16/11/2017 às 18:43

2 Respostas 2

7

Me baseei nessa fórmula e cheguei neste algoritmo:

#include <stdio.h>
#include <math.h>

int hiperfatorial(int n) {
    double ret = 1.0;
    do ret *= pow(n, n); while (n-- > 1);
    return (int)ret;
}

int main(void) {
    int n;
    printf("\nDigite um numero: ");
    scanf("%d", &n);
    printf("\nO hiperfatorial desse numero eh: %d", hiperfatorial(n));
}

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

É muito mais fácil fazer algo iterativo do que recursivo, não vejo razão para fazer diferente. Pela fórmula tem que pegar o valor do termo e elevar a ele mesmo. Dá para não usar o pow() que só aceita ponto flutuante, mas não acho que valha a pena.

Fazendo recursivamente:

#include <stdio.h>
#include <math.h>

int hiperfatorial(int n) { return n > 1 ? hiperfatorial(n - 1) * pow(n, n) : 1; }
int main(void) {
    int n;
    printf("\nDigite um numero: ");
    scanf("%d", &n);
    printf("\nO hiperfatorial desse numero eh: %d", hiperfatorial(n));
}
5
  • O seu funciona mas o jeito que o meu professor pediu para ser feito eh por recursividade :(
    – Bruno Lobo
    Commented 16/11/2017 às 18:56
  • Você não escreveu isto na pergunta, eu respondi o que estava nela.
    – Maniero
    Commented 16/11/2017 às 18:57
  • Verdade, coloquei somente no comentário da pergunta acima, de qualquer maneira você consegue saber o porque meu código não muda o valor do resultado?
    – Bruno Lobo
    Commented 16/11/2017 às 18:59
  • Fiz o recursivo.
    – Maniero
    Commented 16/11/2017 às 19:27
  • @BrunoLobo o valor da variável não era atualizado porque você não guardava o retorno da função. Só jogava fora. Não se esqueça que int em C é passado por cópia, então tudo o que você faz na cópia não afeta a variável que a originou Commented 16/11/2017 às 19:41
7

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:

  • >= 8 ou < 0: retorna código de erro (-1)

    long long int hiperfatorial(int n) {
        if (n >= 8 || n < 0) {
            return -1;
        }
        ...
    }
    

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:

definição recursiva de hiperfatorial: 1 caso entrada seja 0, n^n*H(n-1) caso contrário

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);
}
3
  • 1
    bastante coisa. mas tambem seria legal apontar o problema do programa do AP. (que é simplesmente assumir que a chamada por valor vai mudar o valor da variável resultado)
    – jsbueno
    Commented 17/11/2017 às 0:37
  • Eu tinha marcado ele em um comentário falando disso na resposta do Maniero. Obrigado pela dica, vou transpor aqui para esta resposta, mas estou com outra resposta no gatilho. Em breve volto aqui e atualizo Commented 17/11/2017 às 0:40
  • 1
    @jsbueno, melhorou a resposta agora? Dei destaque logo para o ponto inicial da solução do AP Commented 17/11/2017 às 1:58

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .