recursive superfatorial problem

Question

I have a doubt in the realization of this recursive function of mathematics.

Calculation of the superfatorial:

The superfactor of a number N is defined by the product of the first factorial N of N. Thus, the superfactor of 4 is sf(4) = 1! * 2! * 3! * 4! = 288 Make a recursive function that takes a positive integer number N and returns the superfactor of that number.

My code:

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);
}

When calling the function, super (n, n), the value of the superfactor of n is returned correctly. Note that I used two parameters, n and m. The parameter m of auxiliary to perform the function. This is my doubt, for in the question he asks only one parameter (n). I couldn’t think of a way to do it with a super(n) parameter. It’s possible?

Thank you since.

Answer 1

Hello, I would solve creating an additional function, without changing any of this that you posted. It’s basically what you said yourself, only that not doing this on main, there would be called the superfat, which has only a parameter.

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);
}

Answer 2

An alternative is to use a factorial(n) function, and so the super(n) function becomes recursive without needing an auxiliary:

#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;
}

It is worth remembering that this implementation is not optimal, since for each recursion of super() several factorial that have been calculated before are recalculated. (For a real problem involving factorial I imagine the most efficient is to have a set of even tabulated values).

But for your question that answer is enough.

Answer 3

Practically what the user2856432 spoke only that in a more compact way:

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);
}

Answer 4

This may not have as much relevance in this case (because the factor value - and consequently the superfatorial - grows so fast that it is impracticable to calculate it for large numbers), but the way you and the other respondents are calculating has an inefficiency, which is to calculate again and again components used in various parts of the calculation (as already pointed out by user2856432). When calculating 4! for example you already calculate 3!, best use this result after calculating 3! again in the next term. The complexity in the case is quadratic with the argument value.

I’m going to show you an alternative here, not so much because of the problem itself (which, as I said, is impossible to do for large numbers) but to demonstrate a very useful technique when working with recursion - the accumulator:

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);
}

Explaining, in case it is not clear what the code is doing:

• The initial call passes 0! = 1 as accumulator, and the interval goes from 1 to n;
• The first call - term 1 - multiplies this (n-1)! = (1-1)! = 0! by the result of the recursive call, which in turn receives as accumulator n*(n-1)! = 1*(1-1)! = 1*0! = 1!;
  • The result is 0! * sfat(1)
• The second call - term 2 - multiplies this (n-1)! = (2-1)! = 1! by the result of the recursive call, which in turn receives as accumulator n*(n-1)! = 2*(2-1)! = 2*1! = 2!;
  • The result is 0! * 1! * sfat(2)
• The third call - term 3 - multiplies this (n-1)! = (3-1)! = 2! by the result of the recursive call, which in turn receives as accumulator n*(n-1)! = 3*(3-1)! = 3*2! = 3!;
  • The result is 0! * 1! * 2! * sfat(2)
• ...
• The umpteenth call - term n - multiplies this (n-1)! by the result of the recursive call, which in turn receives as accumulator n*(n-1)!;
  • The result is 0! * 1! * 2! * ... * (n-1)! * sfat(n+1)
• The next call - term n+1 - finds the stopping condition, returning the accumulator ((n+1) - 1)! = n!;
  • The result is 0! * 1! * 2! * ... * (n-1)! * n!

As you can see, the number of recursive calls is now linear with the argument value.

Note: if you wanted to implement the tail recursion - where the recursive call is the last executed operation (useful in languages whose compiler optimizes this type of call, turning it into iterative) - you could do this through two accumulators: one for the factorial, and the other pro result:

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);
}

Examples in the ideone.