Search code examples
javascriptmathcomputer-scienceparadigms

How to express recursive calls in higher dimensions


Just a question of curiosity, not serious.

In the JS language I know that a factorial operation can be defined in the following form.

function factorial(n) {
    if (n === 1) return 1;
    return factorial(n - 1) * n;
}

Then I defined a factorial of a factorial operation in the following form, and called it super_factorial_1. There is a similar description on Wikipedia.

function super_factorial_1(n) {
    if (n === 1) return factorial(1);
    return super_factorial_1(n - 1) * factorial(n);
}

Similarly, using the super_factorial_1 as an operator, the super_factorial_2 is defined here:

function super_factorial_2(n) {
    if (n === 1) return super_factorial_1(1);
    return super_factorial_2(n - 1) * super_factorial_1(n);
}

Now the question is how to define the super_factorial_n operation, and the super_factorial_n_n, and furthermore, the super_factorial_n..._n{n of n}.

I have used a crude method to define the above super_factorial_n operation, but I don't think this method is good enough.

function super_factorial_n(n, m) {
    const fns = Array(n + 1).fill(0);
    fns[0] = factorial;
    for (let i = 1; i <= n; i++) {
        fns[i] = function (m) {
            if (m === 1) return fns[i - 1](1);
            return fns[i](m - 1) * fns[i - 1](m);
        }
    }
    return fns[n](m);
}

Perhaps this is an optimisation direction for the process programming paradigm. :)


Solution

  • The pseudo code

    // j is the level number
    // i = j - 1
    function super_factorial_j(n) {
        if (n === 1)
            return super_factorial_i(1);
        return super_factorial_j(n - 1) * super_factorial_i(n);
    }
    

    Parameterize the j and i

    function super_factorial(j, n) {
        if (n === 1)
            return super_factorial(j - 1, 1);
        return super_factorial(j, n - 1) * super_factorial(j - 1, n);
    }
    

    Add the exit condition

    function super_factorial(j, n) {
        if (j == 0) { // or j == 1 for one based level number
            if (n === 1)
                return 1;
            return super_factorial(0, n - 1) * n;
        }
        if (n === 1)
            return super_factorial(j - 1, 1);
        return super_factorial(j, n - 1) * super_factorial(j - 1, n);
    }
    

    Of course this is just one of the many ways to go. And it is hard to say if this is better then any other one. Recursive functions are generally stack memory consuming. But the value are likely grow very fast, it is not very practice to call it with big numbers anyway.