How to change this nested recursion to linear recursion?

Question

I want to change this function of nested recursion to linear recursion or optimally is tail recursion.

long long x(int n) {
    if (n == 0) return 1;
    int ret = 0;
    for (int i = 0; i < n; ++i) {
        ret += (n - i) * (n - i) * x(i);
    }
    return ret;
}

the origin recursion is

X(0)=1; X(n)=n^2*X(0)+(n-1)^2*X1+...+1^2*X(n-1)

Answer 1

Here you go, converted to tail recursion by using an accumulator variable to store the intermediate results of the computation

long long x(int n, int i, long long acc) {
    if (i == n) return acc;
    return x(n, i + 1, acc + (n - i) * (n - i) * x(i));
}

long long x(int n) {
    return x(n, 0, 1);
}