Hyperfactor in C by recursion

Question

I’m trying to make a program with a recursive function to return a hyperfactor of a number in C, but the only value the function returns is 1. Where I’m missing?

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

Answer 1

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

Every variable in C is passed by value, not by reference (more on the subject). What is called reference passage in C is the passage of the variable pointer into the function. The address where the memory is stored is then modifiable. But, if you analyze how the pointer is passed, it itself is passed by value, making a copy of the pointer value into the function.

---

The first thing I decided to see is how fast the hyperfactor function grew. I found then this article in Mathworld, that led me to that OEIS sequence. I’ll put the values here 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 blew the storage capacity of a long int (32 bits)!! With 7 we have reached the 64 bit storage capacity limit. I did not see the value for H(8), but it will surely blow and plenty the capacity of the long long int.

Note that the amount of bits needed to store the information of a number n any is floor(log2(x)) + 1. Then 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 doesn’t want you to implement an integer with arbitrary capacity, then let’s go to a solution that respects the boundaries of the integer representation using only integer arithmetic.

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

Also, internally I will need to use an entire potentiation function. I will start with it.

Naively, the whole potentiation function could be done so:

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 run in o(lg(expoente)) multiplication operations.

The alternative to this is:

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

I will take the values as the basis of the recursion:

• 0: always returns 1
• 1: returns the base value
• 2: returns the base value multiplied by itself

It would look 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 int_pow is also a pure function, but as it is only used internally, it is not interesting to me.

Now, the code for hiperfatorial. The first step are the basic cases:

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

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

The other cases will be made through the memoization. I will call the memoization vector of this function memo_hiperfatorial. As only the values in the range are interested [0, 7] and the basic case is hiperfatorial(0) = 1, let’s start the vector with zero values for all cases, except memo_hiperfatorial[0], worthwhile 1. The boot 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 for her on the compilation drive, but being static she can quietly stay in function.

Advancing a little further in the writing of the function, we can assume that previously memoised values can already be returned immediately. A value is identified as memoized case memo_hiperfatorial[n] != 0 (for the context of this response, 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];
    }
    ...
}

Okay, now all that’s left is the recursion-favoring step to reach the next value. By definition, hyperfactorial can be escite like this:

Then the recursive step would be:

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

To update the memoised values:

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

Therefore, putting it all together (and re-capitulating 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);
}

Answer 2

I based myself in that formula and arrived at 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));
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

It’s much easier to do something iterative than recursive, I see no reason to do otherwise. The formula has to take the value of the term and elevate itself. You can not use the pow() that only accepts floating point, but I don’t think it’s worth it.

Recursively:

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