Calculating a nested root in C

Question

I was asked to calculate the following nested root expression using recursion only.

I wrote the code below that works, but they allowed us to use only one function and 1 input n for the purpose and not 2 like I used. Can someone help me transform this code into one function that will calculate the expression? cant use any library except functions from <math.h>.

output for n=10: 1.757932

double rec_sqrt_series(int n, int m) {
    if (n <= 0)
        return 0;
    if (m > n)
        return 0;
    return sqrt(m + rec_sqrt_series(n, m + 1));
}

double helper(int n) {
    return rec_sqrt_series(n, 1);
}

Answer 1

Use the upper bits of n as a counter:

double rec_sqrt_series(int n)
{
    static const int R = 0x10000;
    return n/R < n%R ? sqrt(n/R+1 + rec_sqrt_series(n+R)) : 0;
}

Naturally, that malfunctions when the initial n is R or greater. Here is a more complicated version that works for any positive value of n. It works:

• When n is negative, it works like the above version, using the upper bits to count.
• When n is positive, if it is less than R, it calls itself with -n to evaluate the function as above. Otherwise, it calls itself with R-1 negated. This evaluates the function as if it were called with R-1. This produces the correct result because the series stops changing in the floating-point format after just a few dozen iterations—the square roots of the deeper numbers get so diluted they have no effect. So the function has the same value for all n over a small threshold.

double rec_sqrt_series(int n)
{
    static const int R = 0x100;
    return
        0 < n ? n < R ? rec_sqrt_series(-n) : rec_sqrt_series(1-R)
              : n/R > n%R ? sqrt(-n/R+1 + rec_sqrt_series(n-R)) : 0;
}

Answer 2

Without mathematically transforming the formula (I don't know if it is possible), you can't truly use just one parameter, as for each element you need two informations: the current step and the original n. However you can cheat. One way is to encode the two numbers in the int parameter (as shown by Eric).

Another way is to store the original n in a static local variable. At the first call we save n in this static variable, we start the recursion and at the last step we reset it to the sentinel value:

// fn(i) = sqrt(n + 1 - i + fn(i - 1))
// fn(1) = sqrt(n)
//
// note: has global state
double f(int i)
{
    static const int sentinel = -1;
    static int n = sentinel;

    // outside call
    if (n == sentinel)
    {
        n = i;
        return f(n);
    }

    // last step
    if (i == 1)
    {
        double r = sqrt(n);
        n = sentinel;
        return r;
    }

    return sqrt(n + 1 - i + f(i - 1));
}

---

Apparently static int n = sentinel is not standard C because sentinel is not a compile time constant in C (it is weird because both gcc and clang don't complain, even with -pedantic)

You can do this instead:

enum Special { Sentinel = -1 };
static int n = Sentinel;