4

Estou com uma duvida na realização desta função recursiva de matematica.

Calculo do superfatorial:

O superfatorial de um número N é definida pelo produto dos N primeiros fatoriais de N. Assim, o superfatorial de 4 é sf(4) = 1! * 2! * 3! * 4! = 288 Faça uma função recursiva que receba um número inteiro positivo N e retorne o superfatorial desse número.

Meu código:

int super (int n, int m) {
   if (m == 1) return 1;
   if (n == 1) return super (m - 1, m - 1);
   return n * super(n - 1, m);
}

Ao chamar a função, super (n, n), o valor do superfatorial de n é devolvido corretamente. Observe que utilizei dois parametros, n e m. O parametro m de auxiliar para realização da função. Esta é a minha dúvida, pois na questão ele pede apenas um parametro (n). Eu não consegui pensar em uma maneira de faze-la com um paramentro super(n). É possivel?

Agradeço desde ja.

4
  • 1
    Duas tags de duas linguagens diferentes, o problema pode ser resolvido em qualquer uma das duas?
    – DaviAragao
    Commented 7/09/2015 às 15:19
  • Você tem que fazer tudo em uma única função ou podem ser duas? Por exemplo, um fatorial e a superfatorial? Commented 7/09/2015 às 16:12
  • A ideia do exercio é essa.
    – MSX
    Commented 7/09/2015 às 16:39
  • 1
    chama-lhe superauxe cria outra função int super(int n){ return superaux(n,n);}
    – JJoao
    Commented 8/09/2015 às 11:31

4 Respostas 4

4

Olá, eu resolveria criando uma função adicional, sem mudar nada desta que você postou. É basicamente o que você mesmo falou, só que não fazer isso no main, lá seria chamada a superfat, que tem só um parâmetro.

int super (int n, int m) {
   if (m == 1){
        return 1;
   }
   if (n == 1){
        return super (m - 1, m - 1);
   }
   return n * super(n - 1, m);
}

int superfat (int n){
    return super(n, n);
}

int main(){

    printf("%d", superfat(4)); //288

    return(0);
}
3

Uma alternativa é usar uma função fatorial(n), e assim a função super(n) fica recursiva sem precisar de uma auxiliar:

#include <stdio.h>

int fact(n) {
    if(n == 0) {
        return 1;
    }

    //return n*fact(n-1); /* descomentar aqui se preferir definição recursiva (pior performance) /*

    int result = 1;
    while (n > 0) {
        result = n*result;
        n--;
    }
    return result;
}

int super(n) {
    if(n == 0) {
        return 1;
    }
    return fact(n)*super(n-1);
}

int main() {
    printf("Result fact(%d): %d\n", 4, super(4));
    return 0;
}

Vale lembrar que esta implementação não é ótima, visto que a cada recursão de super() diversos fatoriais que já foram calculados antes são novamente calculados. (Para um problema real que envolva fatorial eu imagino que o mais eficiente seja ter um conjunto de valores tabelados mesmo).

Mas para sua pergunta essa resposta é suficiente.

1

Isso pode não ter tanta relevância nesse caso (pois o valor do fatorial - e consequentemente do superfatorial - cresce tão rápido que é inviável calculá-lo para números grandes), mas o modo como você e os demais respondentes estão calculando possui uma ineficiência, que é calcular de novo e de novo componentes usados em diversas partes do cálculo (como já apontado por user2856432). Ao calcular 4! por exemplo você já calcula 3!, melhor usar esse resultado depois que calcular 3! novamente no próximo termo. A complexidade no caso é quadrática com o valor do argumento.

Vou mostrar uma alternativa aqui, nem tanto pelo problema em si (que como já falei, é inviável fazer para números grandes) mas para demonstrar uma técnica muito útil quando se trabalha com recursão - o acumulador:

int sfat(n) {
    return sfat2(1, n, 1); // Vai de 1 a n, e o valor acumulado é 1
}

int sfat2(inicio, fim, acumulador) {
    if ( inicio > fim )
        return acumulador;
    return acumulador * sfat2(inicio+1, fim, inicio*acumulador);
}

Explicando, caso não tenha ficado claro o que o código está fazendo:

  • A chamada inicial passa 0! = 1 como acumulador, e o intervalo vai de 1 a n;
  • A primeira chamada - termo 1 - multiplica esse (n-1)! = (1-1)! = 0! pelo resultado da chamada recursiva, que por sua vez recebe como acumulador n*(n-1)! = 1*(1-1)! = 1*0! = 1!;
    • O resultado é 0! * sfat(1)
  • A segunda chamada - termo 2 - multiplica esse (n-1)! = (2-1)! = 1! pelo resultado da chamada recursiva, que por sua vez recebe como acumulador n*(n-1)! = 2*(2-1)! = 2*1! = 2!;
    • O resultado é 0! * 1! * sfat(2)
  • A terceira chamada - termo 3 - multiplica esse (n-1)! = (3-1)! = 2! pelo resultado da chamada recursiva, que por sua vez recebe como acumulador n*(n-1)! = 3*(3-1)! = 3*2! = 3!;
    • O resultado é 0! * 1! * 2! * sfat(2)
  • ...
  • A enésima chamada - termo n - multiplica esse (n-1)! pelo resultado da chamada recursiva, que por sua vez recebe como acumulador n*(n-1)!;
    • O resultado é 0! * 1! * 2! * ... * (n-1)! * sfat(n+1)
  • A chamada seguinte - termo n+1 - encontra a condição de parada, retornando o acumulador ((n+1) - 1)! = n!;
    • O resultado é 0! * 1! * 2! * ... * (n-1)! * n!

Como você pode ver, o número de chamadas recursivas agora é linear com o valor do argumento.

Nota: se você quisesse implementar a recursão de cauda - em que a chamada recursiva é a última operação executada (útil em linguagens cujo compilador otimiza esse tipo de chamada, transformando-a em iterativa) - você poderia fazer isso através de dois acumuladores: um para o fatorial, e outro pro resultado:

int sfat(n) {
    return sfat2(1, n, 1, 1); // Acumula (n-1)! e o resultado
}

int sfat2(inicio, fim, fat_acc, sfat_acc) {
    if ( inicio > fim )
        return sfat_acc;
    return sfat2(inicio+1, fim, inicio*fat_acc, inicio*fat_acc*sfat_acc);
}

Exemplos no ideone.

1

Praticamente o que o user2856432 falou só que de maneira mais compacta:

int fat(int val){
       if(!val) return 1;
       else return val * fat(val-1);       
}

int sfat(int val){
       if(!val) return 1;
       else return fat(val) * sfat(val-1);
}

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 .