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

Hormone

Can someone help me transform this code into one function that will calculate the expression? what? Help you get rid of the helper? – Grummet

If the arguments are wrong, i would call abort() (from <stdlib.h>), not silently return 0. – Redhot

@Grummet yes exactly, get rid of the helper and only use 1 input n, instead of using n and m. – Hormone

@Redhot can't use any library except of <math.h>. so if you have a solution with that it will be great – Hormone

Your teacher probably means not using any mathematics related library that might supply part of the solution somehow. Surely you can use <stdio.h> and printf to test your code, right? – Redhot

@Redhot yes, i can use only <stdio.h>, <math.h>, printf. – Hormone

@pastaleg Thanks for the heads up - did not notice recursion requirement. – Lowestoft

no problem @chux-ReinstateMonica, sitting here myself trying to figure out if it is viable – Reek

@Reek confident it is - just twisted. – Lowestoft

@chux-ReinstateMonica: what do you think of my twisted solutions? – Antineutrino

@chqrlieforyellowblockquotes Twisied. @Reek How about useless recursion? double nested_root(unsigned n) { double x = 0.0; if (n > 0) { x = nested_root(0); for (unsigned i = n; i > 0; i--) { x = sqrt(i + x); } } return x; } – Lowestoft

@chux-ReinstateMonica: yes, a simpler abuse of the rules. – Antineutrino

My guess is this is not really about the code, but about identifying a non-recursive definition for the series. – Cheboksary

@Oppen: If the goal of the assignment were to fund a non-recursive expression of the function, it probably would not request that the problem be solved using “recursion only.” Certainly a simple loop would calculate the result easily. Although I am generally suspicious when these questions are posted to Stack Overflow without the actual text of the assignment. – Paterfamilias

@EricPostpischil you're right. And you're right in being suspicious, too. – Cheboksary

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, the function works like the above version, using the upper bits to count.
• When n is positive and less than R, the function calls itself with -n to evaluate the series as above. When n is not less than R, the function 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;
}

Paterfamilias

Good idea, but assumes 32-bit ints :) – Antineutrino

@chqrlieforyellowblockquotes: Nah, that is why R is separate, so it can be tuned. Before n reaches 32, the return value stops changing for IEEE-754 binary64, and before it reaches 256, the return value stops changing for reasonable formats for double. So I am considering an alternate version that transforms clamps inputs above R, but it needs to use the sign bit, and I am still working on it. – Paterfamilias

There are other pairing functions you can use, but none as simple as yours. Their main advantage is typically that they work with arbitrary precision, but OP never mentioned that as a requirement. – Grosz

@chqrlieforyellowblockquotes: Done. Now produces the correct answer for any positive n regardless of the width of int. – Paterfamilias

Answer 2

This problem begs for contorted solutions.

Here is one that uses a single function taking one or two int arguments:

• if the first argument is positive, it computes the expression for that value
• if the first argument is negative, it must be followed by a second argument and performs a single step in the computation, recursing for the previous step.
• it uses <stdarg.h> which might or might not be allowed.

Here is the code:

#include <math.h>
#include <stdarg.h>

double rec_sqrt_series(int n, ...) {
    if (n < 0) {
        va_arg ap;
        va_start(ap, n);
        int m = va_arg(ap, int);
        va_end(ap);
        if (m > -n) {
            return 0.0;
        } else {
            return sqrt(m + rec_sqrt_series(n, m + 1));
        }
    } else {
        return rec_sqrt_series(-n, 1);
    }
}

Here is another solution with a single function, using only <math.h>, but abusing the rules in a different way: using a macro.

#include <math.h>

#define rec_sqrt_series(n)  (rec_sqrt_series)(n, 1)
double (rec_sqrt_series)(int n, int m) {
    if (m > n) {
        return 0.0;
    } else {
        return sqrt(m + (rec_sqrt_series)(n, m + 1));
    }
}

Yet another one, strictly speaking recursive, but with single recursion level and no other tricks. As Eric commented, it uses a for loop which might be invalid under the OP's constraints:

double rec_sqrt_series(int n) {
    if (n > 0) {
        return rec_sqrt_series(-n);
    } else {
        double x = 0.0;
        for (int i = -n; i > 0; i--) {
            x = sqrt(i + x);
        }
        return x;
    }
}

Antineutrino

yes that works i guess. thank you very much for all the help – Hormone

Last double rec_sqrt_series(int n), IMO, meets OP's goals by using the sign as a recursion flag. (I'd drop the else as not needed as return is in if.) – Lowestoft

@chux-ReinstateMonica: dropping the else is possible of course but I kinda like to symmetry of both branches of the if returning a result, sort of functional programming style. – Antineutrino

@chux-ReinstateMonica: I expect the assignment’s requirement of “recursion only” precludes iteration. – Paterfamilias

@EricPostpischil: yes, I thought the same, but did not get feedback from the OP. – Antineutrino

Answer 3

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;

Fax

Interesting approach, but I'm afraid the initializer static int n = sentinel; is not fully conformant in C because sentinel is not a constant expression as per the C Standard. It works in C++, and it compiles with current versions of gcc and clang in C mode but not MSVC 2017, but you should probably write static int n = -1; see godbolt.org/z/8pEMnz – Antineutrino

@chqrlieforyellowblockquotes ish. Thank you for pointing this out. Interesting compiler behavior. I've asked about this in this question: https://mcmap.net/q/1173392/-can-a-static-variable-be-initialized-with-a-static-constant/2805305 – Fax

Answer 4

Here is another approach.

It relies on int being 32 bits. The idea is to use the upper 32 bit of a 64 bit int to

1) See if the call was a recursive call (or a call from the "outside")

2) Save the target value in the upper 32 bits during recursion

// Calling convention:
// when calling this function 'n' must be a positive 32 bit integer value
// If 'n' is zero or less than zero the function have undefined behavior
double rec_sqrt_series(uint64_t n)
{
  if ((n >> 32) == 0)
  {
    // Not called by a recursive call
    // so start the recursion
    return rec_sqrt_series((n << 32) + 1);
  }

  // Called by a recursive call

  uint64_t rn = n & 0xffffffffU;

  if (rn == (n >> 32)) return sqrt(rn);      // Done - target reached

  return sqrt (rn + rec_sqrt_series(n+1));   // Do the recursive call
}

Grummet

Answer 5

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

double helper(int n, int i) {
    if (n == 1) {
        return 0;
    }
    return sqrt(helper(n - 1, i + 1) + i);
}

Harm

The question states in bold “use only one function.” – Paterfamilias

@EricPostpischil I know, it's tricky. I got the same assignment at Uni and this is how they wanted us to implement it. I assume it's the same Uni because of the person's username. – Harm