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.
superaux
e cria outra funçãoint super(int n){ return superaux(n,n);}