Hiperfatorial in C by recursion

I based in this formula and I came up with this algorithm:

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

See running on ideone . Also put it on GitHub for future reference .

It's much easier to do something iterative than recursive, I see no reason to do anything different. By the formula you have to take the value of the term and raise it to itself. You can not use the pow() that only accepts floating point, but I do not think it's worth the penalty.

Recursively doing:

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

About your solution, you are not redeeming the value of the function in a variable. It seems that you have an idea implicit in your code that the value of the variable resultado is being changed in the recursion stack, but it does not.

Every variable in C is passed by value, not by reference ( more on the subject ). What is called a by-reference in C is the passing of the variable's pointer into the function. The address at which the memory is stored is then changeable. But if you look at how the pointer is passed, it itself is passed by value, making a copy of the pointer's value into the function.

The first thing I decided to see is how fast the hyperfatorial function grew. I then found this article in MathWorld , which led me to this sequence of OEIS . I'm going to put here the values n , H(n) and 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       |
+---+---------------------+------------+

This means that with the input argument 6 , we pop up the storage capacity of a long int (32 bits) !! With 7 we reach the limit of 64-bit storage capacity. I did not get to see the value for H(8) , but it is sure to burst and much capacity long long int .

Note that the amount of bits needed to store the information of a number n any is floor(log2(x)) + 1 . So we can transform the table above to accommodate the amount of 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      |
+---+------------+---------+

Assuming the question does not want you to implement an integer with arbitrary capability, then let's go to a solution that respects the integer representation boundaries using integer arithmetic.

The hiperfatorial function is a pure function , therefore subject to memoisation. I will set a -1 error code when trying to use a number known to give numerical overflow .

In addition, internally I will need to use an entire power-up function. I'll start with it.

Naive, the whole power-up function could be done like this:

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

This alternative is naive because it always does O(expoente) multiplication operations. We can improve this alternative to execute% multiplication operations with%.

The alternative to this is:

• split the exponent into two
• calculate this exponentiation with this half of the exponent
• multiply the previous result by itself
• If the exponent is odd, multiply the previous result by the base

I'm going to take the values as the basis of the recursion:

• o(lg(expoente)) : always returns 0
• 1 : returns the base value
• 1 : returns the base value multiplied by itself

It would be like this exponentiation:

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 that 2 is also a pure function, but since it is only used internally, it is not interesting to me.

Now, the code for int_pow . The first step is the basic cases:

• hiperfatorial or >= 8 : returns error code ( < 0 )

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

The remaining cases will be done through memoisation. I'll call the memoization vector of this -1 function. Since only values in the memo_hiperfatorial range and the base case are [0, 7] , let's start the vector with zero values for all cases except hiperfatorial(0) = 1 , which is memo_hiperfatorial[0] . The initialization I chose is like this:

static long long int memo_hiperfatorial[8] = { 1, 0, 0, 0, 0, 0, 0, 0 };

I put the variable as static to isolate it. I thought initially of it in the compilation unit, but being static it can quietly stay in the function.

Advancing a little more in the function writing, we can assume that previously memorized values can already be returned immediately. A value is identified as memo if 1 (for the context of this answer, there are other alternatives with other strategies) .

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];
    }
    ...
}

Now, all you need is the step that favors recursion to reach the next value. By the definition, hyperfatorial can be escita like this:

Then the recursive step would be:

return int_pow(n, n) * hiperfatorial(n - 1);

To update the memo values:

return memo_hiperfatorial[n] = int_pow(n, n) * hiperfatorial(n - 1);

So, putting everything together (and recapping memo_hiperfatorial[n] != 0 ):

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